Coding Interview Club

Prepare for coding interviews in simple and structured steps

Merge Sort Algorithm

Problem: 

To understand merge sort completely you should be thorough about the concepts of recursion and the concept of divide and conquer. The basic idea is to divide the array into smaller segments recursively until there is only 1 element in each array segment. Then the array segments with single elements are merged in sorted form to form bigger and bigger sorted array segments.

Approach: 

To understand merge sort completely you should be thorough about the concepts of recursion and the concept of divide and conquer.  If you are not sure about these concepts, then, go and learn or at least read about it, and then come back and learn this algorithm.

The basic idea is to divide the array into smaller segments recursively until there is only 1 element in each array segment. Then the array segments with single elements are merged in sorted form to form bigger and bigger sorted array segments. During every merge, we will be combining two sorted arrays and creating a combined sorted array.

We will see the code for merge sort in java now and then try to understand it.  

Solution: 

Java Program for Merge Sort

public static void mergeSort (int arr[], int low, int high){

               int mid;

               if (low< high){

                              mid= (low+high)/2;

                              mergeSort (arr, low, mid);

                              mergeSort (arr, mid+1, high);

                              merge (arr, low, mid, high);

               }

}

public static void merge (int arr[], int low, int mid, int high){

               int size = high-low+1;

               int temp[] = new int [size];

               int currentLow=low;

               int currentHigh=mid+1;

               int current=0;

               while ( (currentLow <=mid) && (currentHigh <=high) ){

                              if (arr [currentLow ]< arr [currentHigh]){

                                             temp [current] = arr[currentLow];

                                             currentLow++;

                              }

                              else{

                                             temp [current]=arr [currentHigh];

                                             currentHigh++;                                            

                              }

                              current++;

               }

               //If currentHigh has reached high first

               while (currentLow <= mid){

                              temp[current]=arr[currentLow];

                              currentLow++;

                              current++;

               }

               //if currentLow has reached mid but currentHigh has not reached high, we can leave remaining

               // elements in their current sorted position, copy sorted elements to arr.

               for ( int i=0; i< current; i++){

                              arr [low] =temp[i];

                              low++;

               }

}

 

We use the input array and a temporary buffer array to do merge sort. We divide the array in half, sorts each of those halves using recursion, and then merges them back together. Eventually you merge two single element arrays as you keep on dividing and calling mergeSort through recursion.

Every time, we will merge back two sorted segments of the input array. We will copy the sorted segments to a new temporary array in sorted order, and then we will write them back to the original array. First while loop execute

First we divide the input array and then we will merge it in sorted form. The recursive division is done by the below code segment:

if (low< high){

  mid= (low+high)/2;

  mergeSort (arr, low, mid);

  mergeSort (arr, mid+1, high);

Low < high checks for recursion termination condition, which means, as long as there are more than one element, divide and call recursion again.

[67544321]

 [6754]    [4321]

 [67]    [54]    [43]    [21]   

 [6]    [7]    [5]    [4]    [4]    [3]    [2]    [1]   

 

Merge is done by the merge method which is called after all the recursive calls. The merge method simply takes two sorted array segments and creates a merged sorted array. First it will combine two one element array segments, then merge them with bigger sorted arrays and so on.  

[6]    [7]    [5]    [4]    [4]    [3]    [2]    [1]   

 [67]    [54]    [34]    [21]    

 [4567]    [1234]   

[12344567]

   

In the merge method, we use the input array and a temporary buffer array to do merge. We will copy the sorted segments to a new temporary array in sorted order, and then we will write them back to the original array. First while loop executes until currentLow reaches high i.e, atleast when one of the segment ends. The remaining elements in the other segment will be larger than already added ones and in sorted order. So we can just copy them to the end of the new temporary array. We will do this by copying the remaining elements in segment one (left) to the temp array if currentHigh has reached high. However we don’t have to do this in case currentLow has reached mid. The remaining elements in segment two (right) will be eventually in their current position itself even if we copy them to the new array and copy back to the original array there. Finally, we will copy the contents of new temporary array from its beginning till current (last element added) position, into the original array from low till current.

 

Important Points and Performance

  • Merge sort accesses the date in a sequential manner.
  • Merge sort can be used for sorting a linked list.
  • Merge sort is insensitive to the initial order of input.
  • Merge of the merge sort starts with the small sub-lists and finishes up with the largest one and hence it doesn’t need stack. Hence this algorithm is more stable than similar ones like quicksort.
  • Performance of Merge sort is 0 (n log n) in all cases.

 

How to learn an algorithm faster and easier?

Every time you learn an algorithm, the best approach to understand it is to try it out using a pen and paper. Take a sample input; go through each step and iteration writing down all variable values. After each of the iterations, you will understand more and more.

Here first take an array with two sorted array segments and merge them using the merge sort. For instance,  [45671234], with low = 0, mid = 3, high = 7.   

Check out the note on Dijkstra's algorithm to see how you can do this. Or let me know and I will help.

Back to Top