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.

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.Allison
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 Sunday, 27-Nov-2022 05:21:51 AEDT.