Taken from Knuth Algorithm S mergesort P162-163 Vol 3 Second edition 1998
The major change is that the scratch buffer is not required to be adjacent and there are some changes because C array indexing usually starts with 0. This is very much how a mathematician write code. You have to remember a larger than usual single letter variables and it has a very clever clockwork mechanism as the algorithm shifts between using the two arrays as source and destination, and as it merges in both directions (which seems cache foolhardy). It’s pretty efficient even so.
//x is the list to sort, z is a scratch list, N is the number of elements
inline static void kmsort(sort_t *restrict x, sort_t *restrict z, const int N)
{
int s,p; //s=0 if from x to scratch, p is sublist size
int i, j;
int k, l; //2 sublists start,end
int d; // direction of merging
int q, r; // remaining elements of list 1 and 2 to merge
sort_t *R,*D; //the rource and destination array
L1: s = 0; p = 1;
L2: if (!s) { R = x; D = z; } else { R = z; D = x; }
i = 0; j = N - 1; k = -1; l = N; d = 1; q = p; r = p;
L3: if (!LEQ(R [i], R[j]))
goto L8;
L4: k += d;
D[k] = R[i];
L5: i += 1;
q -= 1;
if (q > 0)
goto L3;
L6: k += d;
if (k == l)
goto L13;
else
D[k] = R[j];
L7: j -= 1;
r -= 1;
if (r > 0)
goto L6;
else
goto L12;
L8: k += d;
D[k] = R[j];
L9: j -= 1;
r -= 1;
if (r > 0)
goto L3;
L10: k += d;
if (k == l)
goto L13;
else
D[k] = R[i];
L11: i += 1;
q -= 1;
if (q > 0)
goto L10;
L12: q = p;
r = p;
d = -d;
{
int temp = k;
k = l;
l = temp;
}
if ((j - i) < p)
goto L10;
else
goto L3;
L13: p = p + p;
if (p < N) {
s = 1 - s;
goto L2;
} else {
if (s == 0) { //copy back from scratch
for (i = 0; i < N; i++) {
x[i] = z[i];
}
}
}
return; //done
}
Kuth’s Merge Sort in C