Merge sort algorithm


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(n2) 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 

  1. Splitting
  2. Sorting
  3. Merging.
It’s based on the fact that the arrays with 0 or 1 elements are always sorted. To get an array of 1 element it splits the array till it gets an array of 0 or 1 element. Once these arrays have been formed, It builds up a new sorted array.
 

Example:-

Take below example. We need to sort number from 1 to 7 in increasing order. See in the beginning we divide the array into two halves. one consisting 4,1,7,5 and another having 3,2,6. Now these individual arrays are again split into two arrays. This process is repeated till we get the arrays having 0 or 1 element. Once this process is done we will merge the arrays taking advantage of the fact that arrays with one element are already sorted. merging process is repeated till we get the sorted array.
 
Merge sort animation from https://gifimage.net/merge-sort-animation-gif-4/

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:-

  1. Firstly, Take an empty result array , take a look at each and every smallest value in the input arrays.
  2. 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.
Now that we have seen the pseudo code for merging two arrays, Let’s write the pseudocode for the merge sort.
 

Pseudocode for merge sort:-

We will be using the recursive approach to solve the merge sorting. First, sort the first left half of the array and then go for the next right half and merge them at the end.  The step by step process for merge sort is as follows.
  1. Break arrays into two halves until we have subarrays consisting one or zero elements.
  2.  Once you have the subarrays merge them using the merging arrays pseudocode.
  3.  Finally, the array which is merged is sorted so return back the sorted array.
Implementations are as followed. 
import java.util.Arrays;
public class MergeSort {
public static int[] mergeArrays(int[] a, int[] b) {
int lengthOfFirstArray=a.length;
int lengthOfSecondArray=b.length;
int[] result= new int[lengthOfFirstArray+lengthOfSecondArray];
int i=0;
int j=0;
int 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;
}
 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
return mergeArrays(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:-

Most importantly, As we have discussed above in the pseudocode of the merge sort, Merge sort works on divide and conquer process. So the time complexity of merge sort would be the 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.

Merge sort time and space complexities.

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.