Merge Sort

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

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.
-
Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

© 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 Friday, 29-Mar-2024 10:30:35 AEDT.