### Merge Sort

 LA home Computing Algorithms  glossary  Sorting   Insertion   Quick   Merge   Heap   Dutch N.F.   Radix   Merge sort also see   in-situ

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