Merge Sort Explained.

Merge Sort is one of the well-known sorting algorithms that is based on the Divide and Conquer algorithm. This sorting algorithm divides the given array into two halves and calls itself on those two halves until the array can’t be broken down any further. At last, the two halves are merged to get a sorted array as a result.

Merge Sort Algorithm

MergeSort(A[], start, end){
   if end > start :
      1. Find the middle point of the array
         middle = (start+end)/2;
      2. Call the MergeSort function for the first half
         Mergesort(start, mid);
      3. Call the MergeSort function for the second half    
         MergeSort(mid+1, end);
      4. Merge the two halves
         merge(A[], start, mid, end);
}

Let us break down this algorithm into two parts. The first part will deal with dividing the arrays and the second part will deal with conquering those subarrays.

Divide: Here, step no. 2 and step no. 3 recursively call the MergeSort function on each half of the given array until only one element is left in the array.

Conquer: We will then merge the smaller arrays to get a sorted array using the merge step.

MERGE STEP: The merge step is the most important step in the merge sort algorithm. It is used to merge two sorted arrays into a single sorted array. We use a function called merge to execute this step.

Basically, it compares elements from both the arrays and copies the smaller element into an output array. This process continues until the pointer of either array reaches the final element. We can then simply copy the elements left in the other array into our output array.

Merge Function Algorithm

Let us say we are given an array that needs to be broken into two halves and then merged in such a way that the given array is sorted. This is achieved by using the merge function. The algorithm for the merge function is as follows :

merge(arr[], start, mid, end){
   size1 = mid - start + 1;
   size2 = end - mid;
   
   L[size1], R[size2];
   for (x = 0; x < size1; x++)
        L[x] = arr[p + x];
   for (y = 0; y < size2; y++)
        R[y] = arr[mid + 1 + y];
   i = 0;
   j = 0;
   k = start;
   while (i < size1 && j < size2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
   }
   while (i < size1) {
        arr[k] = L[i];
        i++;
        k++;
   }

   while (j < size2) {
        arr[k] = R[j];
        j++;
        k++;
   }
}

The above algorithm explains how the merge step works. After breaking the given array into two halves and copying the elements into two new arrays (L[] and R[]), we initialise three pointers (i, j and k). The first two pointers (i and j) keep track of the newly created subarrays while the third pointer keeps track of the given input array (arr[]).

While either of the pointers doesn't reach the end element, we compare the elements of both the subarrays and copy the smaller element into the sorted array. Finally, we copy the remaining elements into the sorted array to get the final result.

EXAMPLE

Here’s an image that roughly shows the working of merge sort.

Applications of Merge Sort

1. It is used in external sorting.
2. It is used for inversion counting.
3. For sorting linked lists in O(N log N) time.