Merge Sort
November 10, 2009
It is awkward to sort arrays by merge sort, since it requires two arrays, an input array and an output array; merge sort is used far more often to sort linked lists, as in the Standard Prelude. We begin with a function that merges two sub-arrays, left through middle and middle + 1 through right, from an input array into the positions left through right in an output array:
function merge(A,left,middle,right, B,i,j,k) {
i = left; j = middle + 1
while (i <= middle && j <= right)
if (A[i] <= A[j]) B[++k] = A[i++]
else B[++k] = A[j++]
while (i <= middle)
B[++k] = A[i++]
while (j <= right)
B[++k] = A[j++]
for (k = left; k <= right; k++) {
A[k] = B[k]; delete B[k] } }
Here i indexes the first sub-array, j indexes the second sub-array, and k indexes the output array; we take advantage of Awk’s implicit initialization for k = 0. The first while loop runs until one of the sequences ends, the second and third while loops pick up the remainders of the runs, and the fourth while loop copies the output array back to the input array. Notice that we broke our convention, using less-than-or-equal instead of less-than to compare array elements; doing so allows our sort to be stable, with equal elements appearing in the output in the same order as the input.
Given merge, the actual sort function splits the array in two, sorts the two halves recursively, then merges them together:
function mergesort(A,left,right, middle) {
if (left < right) {
middle = int((left + right) / 2)
mergesort(A, left, middle)
mergesort(A, middle + 1, right)
merge(A, left, middle, right) } }
function sort(A,n) { mergesort(A, 1, n) }
If you like, you can move the merge inline and eliminate recursion; l1 and l2 index the lower bounds of the two sub-arrays, u1 and u2 index the upper bounds of the two sub-arrays, k indexes the output array, and g is the gap between the two sub-arrays, which doubles at each pass:
function sort(A,n, l1,l2,u1,u2,k,g,B) {
for (g = 1; g < n; g *= 2) {
k = 0
for (l1 = 1; l1 + g <= n; l1 = u2 + 1) {
l2 = l1 + g; u1 = l2 - 1
u2 = l2 + g - 1; if (u2 > n) u2 = n
while (l1 <= u1 && l2 <= u2)
if (A[l1] <= A[l2])
B[++k] = A[l1++]
else B[++k] = A[l2++]
while (l1 <= u1)
B[++k] = A[l1++]
while (l2 <= u2)
B[++k] = A[l2++] }
while (k < n)
B[++k] = A[l1++]
for (k = 1; k <= n; k++)
A[k] = B[k] } }
All of the code, including the test suite of the prior exercise, is collected at http://programmingpraxis.codepad.org/Wk6rsu1Z, but you can't run it because codepad doesn't provide an Awk interpreter.
Programming Praxis 
An idiotically cumbersome Java mergesort implementation. The private mergesort returns a pointer to the fully sorted (unsegmented) array.
My implementation in C
#define MODCOPY(x,y) (((x) < 0) ? ((x) = (-y)) : ((x) = (y))) typedef struct ElementNode { int key; int link; }element; static void mergesort_imp(element arr[], int left, int right); static void swap(element arr[], int i, int j); void mergesort(element arr[], int left, int right) { int p, q, k; /* arrange the links in sorted order */ mergesort_imp(arr, left, right); /* sort the records in-place according to the links */ p = left-1; k = left; while(arr[p].link) { if(p < k) { p = arr[p].link; continue; } swap(arr, k, p); q = arr[k].link; arr[k].link = p; p = q; k++; } } /* arr[left-1] and arr[right+1] are two artificial nodes at the start and the end of list. A negative link denotes the end of a sublist known to be ordered; a zero link indicates the end of the entire list */ static void mergesort_imp(element arr[], int left, int right) { int i; int s, t , p, q; /* prepare two lists */ arr[left-1].link = left; arr[right+1].link = left+1; /* initially the file is assumed to be unordered, so setting all links to negative value */ for(i = left; i < (right-1); i++) arr[i].link = -(i+2); arr[right-1].link = 0; arr[right].link = 0; /* we have created two lists out of which one list contain all odd positioned elements and other list contain all even positioned elements */ /* main loop */ for(;;) { /* begin new pass */ s = left-1; t = right+1; p = arr[s].link; q = arr[right+1].link; if(q == 0) /* terminate */ break; for(;;) { /* compare keys */ if(arr[p].key > arr[q].key) { MODCOPY(arr[s].link, q); s = q; q = arr[q].link; if(q <= 0) { arr[s].link = p; s = t; do { t = p; p = arr[p].link; } while(p > 0); p = -p; q = -q; } } else { MODCOPY(arr[s].link, p); s = p; p = arr[p].link; if(p <= 0) { arr[s].link = q; s = t; do { t = q; q = arr[q].link; } while(q > 0); p = -p; q = -q; } } if(q == 0) break; } MODCOPY(arr[s].link, p); MODCOPY(arr[t].link, 0); } } static void swap(element arr[], int i, int j) { element temp; temp.key = arr[i].key; temp.link = arr[i].link; arr[i].key = arr[j].key; arr[i].link = arr[j].link; arr[j].key = temp.key; arr[j].link = temp.link; }