**Why not traditional sorting algorithms?**

Firstly, Before getting into the merge sort explanation, Let’s see why traditional sorting algorithms(Bubble, Selection, Insertion sorting) are not the go to algorithms for sorting. The devil that stops using traditional algorithms is “TIME COMPLEXITY”.Yes, All of them have a time complexity of O(n^{2}) along with swapping operations. As a result, as the input size increases the time taken for sorting increases quadratically. This is very bad in case of large inputs. To conclude, Let me give you an example of sorting the number of books in the world by its word count. It is a mammoth task to count number of words in each book in every iteration using traditional sorting algorithms as they take O(n2) time to complete it.

Therefore there should be a better algorithm to speed up this process. In fact there are many as such. But, we will be looking into merge sort in this post.

Meanwhile, If you are new to time complexity or big O notation, I have written an elaborate blog post about it here. Please check it out as time complexity is something that’s very important in understanding any algorithm or data structure.

**Introduction to merge sort:-**

The principle behind the merge sort is “Divide and Conquer”. Basically, merge sort is a combination of 3 operations. They are

- Splitting
- Sorting
- Merging.

**Example:-**

As we have seen in the example merge sort algorithm requires merging arrays. So before getting into the pseudo code of the merge sort, let’s see the pseudocode for merging two sorted arrays.

**Pseudocode for merging two sorted arrays:-**

- Firstly, Take an empty result array , take a look at each and every smallest value in the input arrays.
- while there are values we haven’t looked at yet
**A**. If the value in the first array is smaller than the value in the second array, push the element in the first array into the result array, and continue with the second element in the first array.**B.**Otherwise, If the value in the first array is greater than the value in the second array, push the element from the second array into the result array, and continue with the second element in the second array.**C.**Continue with the remaining elements in the array.

**Pseudocode for merge sort:-**

- Break arrays into two halves until we have subarrays consisting one or zero elements.
- Once you have the subarrays merge them using the merging arrays pseudocode.
- Finally, the array which is merged is sorted so return back the sorted array.

importjava.util.Arrays;publicclassMergeSort {publicstaticint[] mergeArrays(int[] a,int[] b) {intlengthOfFirstArray=a.length;intlengthOfSecondArray=b.length;int[] result=newint[lengthOfFirstArray+lengthOfSecondArray];inti=0;intj=0;intcurrentResultArrayIndex=0;while(i<lengthOfFirstArray && j<lengthOfSecondArray ) {if(a[i]<= b[j]) {

result[currentResultArrayIndex]=a[i];

i=i+1;

currentResultArrayIndex=currentResultArrayIndex+1;

}else{

result[currentResultArrayIndex]=b[j];

j=j+1;

currentResultArrayIndex=currentResultArrayIndex+1;

}

}while(i<lengthOfFirstArray) {

result[currentResultArrayIndex]=a[i];

i=i+1;

currentResultArrayIndex=currentResultArrayIndex+1;

}while(j<lengthOfSecondArray) {

result[currentResultArrayIndex]=b[j];

j=j+1;

currentResultArrayIndex=currentResultArrayIndex+1;

}returnresult;

}public static int[] mergeSort(int[] a) {

if(a.length<=1) {

return a;

}else {

int mid=Math.floorDiv(0, a.length/2); //find the mid point

int[] leftArray=mergeSort(Arrays.copyOfRange(a, 0, mid+1)); // sub array from 0 to mid

int[] rightArray=mergeSort(Arrays.copyOfRange(a, mid+1, a.length)); // sub array from mid to length

returnmergeArrays(leftArray, rightArray);

}

}

public static void main(String[] args) {

int[] a= {4,1,7,5,3,2,6};

for(int j:mergeSort(a)) {

System.out.println(j);

} } }

function mergeArrays(a, b) {

var lengthOfFirstArray = a.length;

var lengthOfSecondArray = b.length;

var result = [];

var i =0;

var j =0;

var currentResultArrayIndex =0;

while (i < lengthOfFirstArray && j < lengthOfSecondArray) {

if (a[i] <= b[j]) {

result[currentResultArrayIndex] = a[i];

i = i + 1;

currentResultArrayIndex = currentResultArrayIndex + 1;

}

else {

result[currentResultArrayIndex] = b[j];

j = j + 1;

currentResultArrayIndex = currentResultArrayIndex + 1;

}

}

while (i < lengthOfFirstArray) {

result[currentResultArrayIndex] = a[i];

i = i + 1;

currentResultArrayIndex = currentResultArrayIndex + 1;

}

while (j < lengthOfSecondArray) {

result[currentResultArrayIndex] = b[j];

j = j + 1;

currentResultArrayIndex = currentResultArrayIndex + 1;

}

return result;

}

function mergeSort(array) {

if (array.length <=1) {

return array;

}

else {

if (array.length <=1) return array;

let mid = Math.floor(array.length /2);

let left = mergeSort(array.slice(0, mid));

let right = mergeSort(array.slice(mid));

return mergeArrays(left, right);

}

}

var a = [4, 1, 7, 5, 3, 2, 600];

console.log(mergeSort(a));

**Time complexity of merge sort:-**

**sum of time complexity of sorting left half of array + time complexity of sorting right half of array + time complexity of merging both sorted arrays.**

Following image explains the time complexity of merge sort.

Thus we can say the time complexity of the merge sort is O(n*log(n)). On observing the time complexity of the merge sort we can say that merge sort is faster than the traditional sorting algorithms.

But however on the other hand the space complexity of the merge sort is o(n) as it requires to sort left and right half of the array and store it for merging them.

To conclude, Merge sort is not an in-place sorting algorithm which is better sorting algorithm in terms of speed but bad in terms of memory utilisation. Thus this sorting algorithm can be used in applications where speed is atmost priority than space consumption.