Mergesort algorithm for linked lists

[Joerg Schoen]

Hi folks!

Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.)
For linked lists, mergesort is the typical choice.

While I was looking for a optimized implementation of mergesort for
linked lists, I couldn't find one. I read something about Mcilroy's
"Optimistic Merge Sort" and studied some implementation, but they
were for arrays. Does anybody know if Mcilroys optimization is applicable to
truly linked lists at all?

Eventually, I came up with my own implementation (see below) which seems to
perform quite well. The algorithm is my own idea - at least I don't know if
anybody else has come up with this before.

The algorithm is localized. It maintains a stack of sorting length and tries
to merge small pieces as soon as possible. This takes advantage of a CPU
caches.

Here are my questions about it:

- Is my implementation new/genuine or has somebody else come up
with this before?

- How does it compare with other optimized implementations (provided there
are such)? I would like to hear from better implementations!

- When optimizing quicksort, one usually tries to use insertion sort
and the like for SMALL parts. I tried to do the same for the mergesort
below, i. e. sort small pieces of length ~ 10 with insertion sort.

It actually became slower I don't quite understand why.

Thanks for any comments!

Joerg

PS: You can find this implementation at
http://www.die-Schoens.de/prg/testsort.tgz

--------------------- snip ------------------------------
#include <stddef.h> /* for NULL */

typedef struct linkedlist_t linkedlist_t;
struct linkedlist_t {
linkedlist_t *Next;
int Key;
};

#define NATURAL /* recognize natural runs */

linkedlist_t *mergesort(linkedlist_t *list)
{
struct {
linkedlist_t *list;
unsigned int size;
#ifdef NATURAL
unsigned int level;
#endif
} stack[sizeof(int) * 8];
int nstack;

for(nstack = -1 ; ; ) {
linkedlist_t *plist, *qlist, *curr;
unsigned int psize, qsize;

/* Can we or do we have to merge lists from the stack? */
if(nstack < 1 || (
#ifdef NATURAL
stack[nstack - 1].level != stack[nstack].level
#else
stack[nstack - 1].size != stack[nstack].size
#endif
&& list != NULL)) {
/* ** Push element(s) on the stack ** */
if(list == NULL)
/* This is where we break the loop. We have nstack == 0 now */
break;

/* ** Push lists of length 1 ** */
curr = list;
psize = 1;

list = list->Next;

#ifdef NATURAL
/* Check for a natural run */
for(plist = curr ; list != NULL ; plist = list, list = list->Next,
++psize)
if(list->Key < plist->Key)
break;

/* Properly terminate the run */
plist->Next = NULL;
#else
/* Properly terminate list */
curr->Next = NULL;
#endif

/* ** Push this run on the stack ** */
++nstack;
stack[nstack].list = curr;
stack[nstack].size = psize;
#ifdef NATURAL
stack[nstack].level = 0;
#endif

continue;
}

/* ** Merge top two entries from stack ** */
plist = stack[nstack].list; psize = stack[nstack].size;
--nstack;
qlist = stack[nstack].list; qsize = stack[nstack].size;

/* ** Set up new stack element. This also simplifies the main loop
below ** */
if(qlist->Key < plist->Key) {
curr = qlist;
qlist = qlist->Next; --qsize;
} else {
curr = plist;
plist = plist->Next; --psize;
}

stack[nstack].list = curr;

/* Number of elements is just the sum */
stack[nstack].size += stack[nstack + 1].size;
#ifdef NATURAL
stack[nstack].level++;
#endif

/* ** Here is the main merging loop ** */
while(psize > 0 && qsize > 0) {
if(qlist->Key < plist->Key) {
curr->Next = qlist; curr = qlist;
qlist = qlist->Next; --qsize;
} else {
curr->Next = plist; curr = plist;
plist = plist->Next;; --psize;
}
}

/* Add remainder to result list */
if(psize > 0) {
curr->Next = plist;
} else {
curr->Next = qlist;
}
}

/* Here we treat the case of list == NULL */
return nstack == 0 ? stack[nstack].list : NULL;
}
-------------------- snap -----------------------