Merge Sort
November 10, 2009
The last O(n log n) sorting algorithm that we shall consider in our current series of exercises is merge sort. If you have two sorted sequences, they can be merged into a single sorted sequence in time linear to their combined length by running through them in order, at each step taking the smaller of the heads of the two sequences. Then mergesort works by recursively merging smaller sequences into larger ones, starting with trivially-sorted sequences of one element that are merged into two-element sequences, then merging pairs of two-element sequences into four-element sequences, and so on, until the entire sequence is sorted.
Your task is to write a function that sorts an array by the merge sort algorithm described above, according to the conventions of the prior exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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; }