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

[Richard Harter]

On Wed, 24 Jan 2007 18:29:20 GMT, cr*@tiac.net (Richard Harter) wrote:

[snip]

>function alpha (list L) returns list
level = 0
out = nil
while (L)
append beta(level,L) to out
level ++
end while
return out

The line
append beta(level,L) to out
should read
out = merge(beta(level,L))

[Richard Harter]

On Mon, 29 Jan 2007 23:15:57 -0000, "Stephen Howe"
<sjhoweATdialDOTpipexDOTcomwrote:

>Um, no, you miss the essential point. The uniqueness lies in the way in
which he accesses the data, not in the fact that he is using natural
mergesort. In fact he conditionalizes whether it is natural or not.

I saw that. But that was via the pre-processor.
Whatever way he compiles it, its behaviour does not change at run-time.
I will re-check mind you.

It is unclear to me what you are trying to say. The behaviour when
NATURAL is defined is different than when it is isn't.

>

>It isn't true that you can't do a natural mergesort for arrays.

Okay, I will go with that. I overstated the case. But lets go over that.

To do natural mergesort with arrays requires an auxilary array where item
records
- the start of a run
- how many elements in the run
as there may be no other place to record that information

This is true - sort of. For the standard recursive and iterative
versions you will need an array whose size is the number of runs (=NR).
For McCarthy versions require an array whose size is log2(NR). In a
recursive McCarthy version the "array" is contained in the recursion
stack. In an iterative there must be an exlicit stack.

>
And there are 2 algorithms with natural mergesort:
- there is the recursive version
- there is the iterative version

Actually there are (at least) 3. In addition:
- there is the McCarthy version

The McCarthy version is (or can be described as being) a hybrid
iterative/recursive version. Both Schoen and Sosman unfold the
recursion.

>
I dont see how to do a recursive version with natural mergesort for arrays.
Because consider the first run - it could be the only run or it could be one
of many.
How many function calls are made recursively depends on the number of runs
and that is not known in advance or as your are going along.

On the iterative version of natural mergesort - you can make 1 pass and
record the index and run length.
After that, you merge adjacent entries and keep doing so until you have 1
run.

In either case the natural way to do things is to operate with the
auxilliary array. The way to think of this is that the merge process
operates on a sequence of elements, where an element is a sorted run.
In vanilla mergesort the element run length is always 1.

>Technically the auxilary array could be O(N) in size in everything is in
reverse order.
The overhead of having to maintain an auxiliary array is quite substantial
but probably less than standard merge sort.