Merge Sort

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

Algorithms
 glossary
 Sorting
  Insertion
  Quick
  Merge
  Heap
  Dutch N.F.
  Radix

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, check the bibliography and 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., Department of Computer Science UWA 1984, Department of Computer Science Monash 1986, and (HTML) Comp. Sci. & Software Eng., Monash University 1999.
-
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Tuesday, 29-Jul-2014 00:23:49 EST.