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 -----------------------