### 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_{2}(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
`[...]`

L . A l l i s o n |

### 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'.