Merge Sort

Merge sort divides the array into two halves which are sorted recursively and then merged to form a sorted whole. The array is divided into equal sized parts (up to truncation) so there are log₂(N) levels of recursion.

It is interesting to compare quick sort with merge sort; the former has a pre-order structure the latter a post-order structure. In fact there is also a bottom-up, breadth-first merge sort.

function merge(int inA[], int lo, int hi, int opA[])
/* sort (input) inA[lo..hi] into (output) opA[lo..hi] */
 { int i, j, k, mid;

   if(hi > lo) /* at least 2 elements */
    { int mid = (lo+hi)/2;          /* lo <= mid < hi */
      merge(opA, lo,   mid, inA);     /* sort the ... */
      merge(opA, mid+1, hi, inA);      /* ... 2 halfs */

      i = lo;  j = mid+1;  k = lo;  /* and merge them */
      while(true)
       { if( inA[i] <= inA[j] )        /* ? smaller ? */
          { opA[k] = inA[i]; i++; k++;
            if(i > mid) /* copy rest */
             { for( ; j <= hi;  j++)
                { opA[k]=inA[j]; k++; }
               break;
             }
          }
         else
          { opA[k] = inA[j]; j++; k++;
            if(j > hi) /* copy rest */
             { for( ; i <= mid; i++)
                { opA[k]=inA[i]; k++; }
               break;
             }
          }
       }/*while */
    }/*if  */
 }/*merge */

function mergeSort(int a[], int N)  /* wrapper routine */
/* NB sort a[1..N] */
 { int i; int b[N];
   for(i=1; i <= N; i++) b[i]=a[i];
   merge(b, 1, N, a);
 }

Change the data in the HTML FORM below, click 'go', and experiment; the section processed by each recursive call is bracketted [...] in the trace:

Complexity

Time

The best, average and worst case time-complexities of the (basic) algorithm are all the same, O(N*log(N)).

Space

The space complexity of the recursive algorithm is O(N+log(N)), N for the "working-space array" and log(N) for the stack space.

A naive non-recursive translation would still use O(N+log(N)) space, log(N) being for an explicit stack. However, because the array sections vary in a simple and systematic way, there is a non-recursive version that does not need any stack and requires O(N) space only (but there again, log(N)<<N, if N is large).

There are in fact in-situ merging algorithms that only use O(1) space but they are difficult!

Stability

Merge sort is stable if written carefully, it is a matter of a '<=' versus a '<'.

Notes

• For papers on in-situ merging in O(1) space, search for 'insitu merge'.
  For a real programming challange, try to devise an algorithm to merge (sorted) A[i..j] and (sorted) A[j+1..k] into A[i..k], only using O(1), i.e. constant, space.
• There are adaptive versions of merge sort that run more quickly on certain kinds of data; check the bibliography and search for 'adaptive sort'.