Merge Sort

LA home
Computing
Algorithms
 glossary
 Sorting
  Insertion
  Quick
  Merge
  Heap
  Dutch N.F.
  Radix
  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 log2(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:

L
.
A
l
l
i
s
o
n
input:  
output:
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'.
© L.A.
-
www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Monday, 22-Jan-2018 19:03:05 EST.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.