Mergesort algorithm for linked lists

[Richard Harter]

I don't think my code has an O(n^2) worst case, even if it is
slower than an "unnatural" merge sort. What do you think could
trigger an O(n^2) case in my code?

I think I take it back; there's an ambiguity in the wording of your
description. If you eat the runs one at a time the worst case is O(n^2)
with a reversed list. Upon reflection I suspect that what you meant was
to each a pair of runs, then another pair of runs, etc. That would
indeed be O(n log n). You didn't specify what you were doing with your
output runs. If you simply plop them back in place, that's expensive.
However you can use a stack (that's what Joerg Schoen is doing), or with
a bit of cheap cleverness you can do a clean recursive routine.

 

[Richard Harter]

I think that you will find that an initially reverse sorted list
will eat up stack and time. You are doing a lot of copying, which
is totally unnecessary. Remember, records can be big.

Perhaps you've forgotten that he is talking about sorting linked lists.
There is no copying involved here, just changing links. Moreover the
maximum stack depth is O(log n). It is true that a initially reverse
sorted list is worst case for an ascending runs mergesort; however the
penalty lies in excessive comparisons.

 

[jo65]

will eat up stack and time. You are doing a lot of copying, which
is totally unnecessary. Remember, records can be big.

As Richard pointed out, I am not doing copying at all, just changing
links. In the test program on my page, I am comparing the mergesort
with other implementations. I use (1) random numbers (2) random numbers
with each value appearing multiple times (3) already sorted list (4)
inverse
sorted list.

It turns out that the implementation behaves well in all cases: It
excells in case (3)
since it recognizes the whole input as one big run and is done. Case
(4) is
"worst case" for the one which tries to recognize natural runs. It is
by ~ 1%
or so slower than the one that collects runs of length 1 and then
doubles on each
iteration. The reason is that the recognition of natural runs only is
done ONCE
over the input, so the "added penalty" is O(n) and the factor is only
the cost of
a comparison.

When time permits (during the weekend most likely), I will put Ben's
implementation
and a "standard text book" one for comparison.

 

[jo65]

However you can use a stack (that's what Joerg Schoen is doing), or with
a bit of cheap cleverness you can do a clean recursive routine.

Triggered by this discussion I realized that I can still improve the
code and
get rid of keeping the lengths of the runs on the stack. So well, here
is my
"improved version". I have also increased the indentation, so it should
be
better readable. Moreover, the preprocessor stuff only appears once
now.

I still would like to know how to do it with a recursive routine,
currently I have
no idea about that.

------------------------ 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 level;
} stack[sizeof(int) * 8];
int nstack;

for(nstack = -1 ; ; ) {
linkedlist_t *plist, *qlist, *curr;

/* Can we or do we have to merge lists from the stack? */
if(nstack < 1 || (stack[nstack - 1].level !=
stack[nstack].level && 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;
list = list->Next;

#ifdef NATURAL
/* Check for a natural run */
for(plist = curr ; list != NULL ; plist = list, list =
list->Next)
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].level = 0;

continue;
}

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

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

stack[nstack].list = curr;
stack[nstack].level++;

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

/* Add remainder to result list */
curr->Next = plist != NULL ? plist : qlist;
}

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

 

[CBFalconer]

Perhaps you've forgotten that he is talking about sorting linked lists.
There is no copying involved here, just changing links. Moreover the
maximum stack depth is O(log n). It is true that a initially reverse
sorted list is worst case for an ascending runs mergesort; however the
penalty lies in excessive comparisons.

He is talking about building stacks, which involves copying
something somewhere. A normal mergesort is basically iterative,
and only diddles pointers. The stack depth is at most log N. At
least as I recall his description.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[CBFalconer]

.... snip ...

Triggered by this discussion I realized that I can still improve
the code and get rid of keeping the lengths of the runs on the
stack. So well, here is my "improved version". I have also
increased the indentation, so it should be better readable.
Moreover, the preprocessor stuff only appears once now.

I still would like to know how to do it with a recursive routine,
currently I have no idea about that.

I suggest you pack this up with your earlier algorithm
documentation and post it somewhere in a zip or tgz file.
Alternatively (and poorer) post them together here in one article.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[jo65]

He is talking about building stacks, which involves copying
something somewhere.

Well, if you call setting variables "copying", I agree that I do copy
data.
But then every program does. The stack in my implementation only
contains a pointer to a list and a stack level, nothing more. No actual
"data" is copied.

A normal mergesort is basically iterative,
and only diddles pointers. The stack depth is at most log N. At
least as I recall his description.

There are recursive implementations and iterative ones of mergesort.

As detailed above, the pure iterative ones are repeatedly running
through
the whole list and have the disadvantage of not being localized thus
not taking advantage of a memory cache. Moreover, there is a lot of
"idle running along the list" in it.

The recursive version of mergesort is localized, but again needs some
idle running.

 

[pete]

As long as we're posting links to linked list merge sorts, my
implementation is at
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/ll.c?rev=1.3&root=pspp&view=markup
in function ll_sort().

It's optimized for readability.

This is what I use:

/* BEGIN list_type.h */

#ifndef H_LIST_TYPE_H
#define H_LIST_TYPE_H

struct list_node {
struct list_node *next;
void *data;
};

typedef struct list_node list_type;

list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *));

#endif

/* END list_type.h */



/* BEGIN list_type.c */

#include <stddef.h>

#include "list_type.h"

static int list_sorted(list_type *list,
int (*compar)(const list_type *, const list_type *));
static long unsigned node_count(list_type *head);
static list_type *node_sort (list_type *head, long unsigned count,
int (*compar)(const list_type *, const list_type *));
static list_type *list_split(list_type *head, long unsigned count);
static list_type *list_merge(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));

list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return
!list_sorted(head, compar)
? node_sort(head, node_count(head), compar)
: head;
}

static int list_sorted(list_type *list,
int (*compar)(const list_type *, const list_type *))
{
if (list != NULL) {
while (list -> next != NULL) {
if (compar(list, list -> next) > 0) {
break;
}
list = list -> next;
}
}
return list == NULL || list -> next == NULL;
}

static long unsigned node_count(list_type *head)
{
long unsigned count;

for (count = 0; head != NULL; head = head -> next) {
++count;
}
return count;
}

static list_type *node_sort(list_type *head, long unsigned count,
int (*compar)(const list_type *, const list_type *))
{
long unsigned half;
list_type *tail;

if (count > 1) {
half = count / 2;
tail = list_split(head, half);
tail = node_sort(tail, count - half, compar);
head = node_sort(head, half, compar);
head = list_merge(head, tail, compar);
}
return head;
}

static list_type *list_split(list_type *head, long unsigned count)
{
list_type *tail;

while (--count != 0) {
head = head -> next;
}
tail = head -> next;
head -> next = NULL;
return tail;
}

static list_type *list_merge(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
list_type *list, *sorted, **node;

node = compar(head, tail) > 0 ? &tail : &head;
sorted = list = *node;
*node = sorted -> next;
while (*node != NULL) {
node = compar(head, tail) > 0 ? &tail : &head;
sorted -> next = *node;
sorted = *node;
*node = sorted -> next;
}
sorted -> next = head != NULL ? head : tail;
return list;
}

/* END list_type.c */

 

[pete]

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.

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

The only lists that I have ever been paid to sort,
were lists of text that needed to be sorted into alphabetical order.

 

[pete]

See the discussion in Knuth on merge sorts.
Natural gains when runs are
long and few and loses when runs are short and many. Offhand your
version is going to much more expensive (though still O(n log n))
because you have to rescan the runs.

When I've done timed tests and comparison counts
for mergesorting lists,
I've found that for random order lists,
that checking for ordered sublists, is bad.

In my experience, when I have had to sort lists,
the situations have been that
the lists had a high probability of already being sorted,
so, I check them once to see if they're sorted and
then if they're not, I don't look for sorted subsections any more.

On the other hand, when quicksorting arrays of integers,
in timed tests I have found
that checking for ordered subarrays, pays off.

 

[Richard Harter]

comp.programming added

Triggered by this discussion I realized that I can still improve the
code and
get rid of keeping the lengths of the runs on the stack. So well, here
is my
"improved version". I have also increased the indentation, so it should
be
better readable. Moreover, the preprocessor stuff only appears once
now.

I still would like to know how to do it with a recursive routine,
currently I have
no idea about that.

As a note I don't see this algorithm in Knuth. IMHO it is quite elegant
and has applications beyond mergesorting. I doubt that it is new; it is
too simple. However I've never seen it in an algorithms text. I
propose to call the general idea Schoen's algorithm.

Here is the outline of the iterative/recursive version in pseudocode.
There are two routines, alpha and beta. Alpha is the iterative outer
loop that is executed log n times. Beta is the recursive part; it
implements the mergesort algorithm as outlined by each of us.

/* each call to beta consumes exponentially growing pieces of L,
sorts them. and adds them to the output.
*/

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

/* At level k > 0 beta makes two calls to beta at k-1, merges the
result,
and returns the merged list. At level 0 it extracts two runs from L,
merges them, and returns the merged list. At any point if there is a

nil return from the first call/extract the second call/extract is not
made.
*/

function beta (int level, list L) returns list
if (not L) return nil
if (level <= 0)
run_1 = extract(L)
if (not L) return run_1
run_2 = extract(L)
else
run_1 = beta(level-1, L)
run_2 = beta(level-1, L)
return merge(run_1,run_2)

The extract function could either extract an ascending run or a
single item from L; the extracted items are removed from L. The
merge function merges two sorted lists and returns the merged list.

One important point in this pseudo code is that L is global to the
various functions. How to avoid this is, AFICT, language dependent.
In procedural languages it is probably best to manually simulate
recursion as (in effect) Joerg Schoen did. I'm not sure exactly how to
implement it in a functional language, but it should be easy.

 

[Stephen Howe]

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.

It is known. This is natural mergesort. Robert Sedgewick talked about it in
one of his books.
You can't do a natural mergesort for arrays but it is dead simple for linked
lists.
You exploit any pre-existing order anywhere. I would be exceptionally
exceptionally surprised if it is not discussed in Kuth's 3rd volume
somewhere.

Best of all, the sort will be O(N) if it is already sorted and it does well
on data that has partial orders.
The worst case for natural mergesort is if the data is in reverse order to
start with. There are no "runs" then.
I would be tempted to do a hybrid where all runs were at least 4 elements no
matter what.
This would be to guard against the reverse order distribution to start with.

Stephen Howe

 

[Richard Harter]

It is known. This is natural mergesort. Robert Sedgewick talked about it in
one of his books.
You can't do a natural mergesort for arrays but it is dead simple for linked
lists.
You exploit any pre-existing order anywhere. I would be exceptionally
exceptionally surprised if it is not discussed in Kuth's 3rd volume
somewhere.

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. It
isn't true that you can't do a natural mergesort for arrays.

 

[Eric Sosman]

Well, I read Sedgewick long ago . However I fail to see how you
can do a merge without first splitting.

Split and merge as you go. See TAOCP (vol III) exercise
5.2.4-17, where the idea is credited to John McCarthy. The
basic McCarthy method has peaks of inefficiency when the list
length is one greater than a power of two (more generally, when
the binary representation of the node count has 1-bits that are
separated by runs of 0-bits), but I've found[*] a simple way to
fix them without losing much speed in the nicer cases. Code
available on request.

[*] I also "found" McCarthy's method for myself before
reading it in Knuth, and for all I know others have found "my"
improvement before I did. The original is a truly pretty
algorithm, a real "Why didn't I think of that?" piece of work.
Highly recommended!

 

[CBFalconer]

Well, I read Sedgewick long ago . However I fail to see how
you can do a merge without first splitting.

Split and merge as you go. See TAOCP (vol III) exercise
5.2.4-17, where the idea is credited to John McCarthy. The
basic McCarthy method has peaks of inefficiency when the list
length is one greater than a power of two (more generally, when
the binary representation of the node count has 1-bits that are
separated by runs of 0-bits), but I've found[*] a simple way to
fix them without losing much speed in the nicer cases. Code
available on request.

[*] I also "found" McCarthy's method for myself before
reading it in Knuth, and for all I know others have found "my"
improvement before I did. The original is a truly pretty
algorithm, a real "Why didn't I think of that?" piece of work.
Highly recommended!

My Knuth is buried in boxes somewhere. Sounds as if the split
mechanism is something like take alternate entries, and my instinct
tells me that this will disturb the stability of the sort, which in
turn is one of the most attractive features of mergesort.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Richard Harter]

Well, I read Sedgewick long ago . However I fail to see how you
can do a merge without first splitting.

Split and merge as you go. See TAOCP (vol III) exercise
5.2.4-17, where the idea is credited to John McCarthy. The
basic McCarthy method has peaks of inefficiency when the list
length is one greater than a power of two (more generally, when
the binary representation of the node count has 1-bits that are
separated by runs of 0-bits), but I've found[*] a simple way to
fix them without losing much speed in the nicer cases. Code
available on request.

[*] I also "found" McCarthy's method for myself before
reading it in Knuth, and for all I know others have found "my"
improvement before I did. The original is a truly pretty
algorithm, a real "Why didn't I think of that?" piece of work.
Highly recommended!

Good catch. I knew it had to be in Knuth somewhere, but some how I
missed it. That is what Schoen is doing, modulo minor variations.

 

[Eric Sosman]

(e-mail address removed) wrote:
Thanks for the comment! Your implementation is basically the one
from Sedgewick's book. It has the disadvantage that you have to
run through the linked lists repeatedly to split it, but it is
also localized, i.e. takes advantage of caches.
Well, I read Sedgewick long ago . However I fail to see how
you can do a merge without first splitting.

Split and merge as you go. See TAOCP (vol III) exercise
5.2.4-17, where the idea is credited to John McCarthy. The
basic McCarthy method has peaks of inefficiency when the list
length is one greater than a power of two (more generally, when
the binary representation of the node count has 1-bits that are
separated by runs of 0-bits), but I've found[*] a simple way to
fix them without losing much speed in the nicer cases. Code
available on request.

[*] I also "found" McCarthy's method for myself before
reading it in Knuth, and for all I know others have found "my"
improvement before I did. The original is a truly pretty
algorithm, a real "Why didn't I think of that?" piece of work.
Highly recommended!

My Knuth is buried in boxes somewhere. Sounds as if the split
mechanism is something like take alternate entries, and my instinct
tells me that this will disturb the stability of the sort, which in
turn is one of the most attractive features of mergesort.

Unbury. "Take alternate entries" just changes the pattern
of splitting (unstably), not the number of split passes. It
makes the same number of node visits (= link traversals) as
"split in the middle" does.

The nice thing about McCarthy's "split mechanism" is that it
makes one count them one pass over the full list instead of the
lg(N) passes of "split in the middle" or "alternate entries."
The resulting sort is stable (assuming you don't do anything dumb).

The un-nice thing about McCarthy's method is that after
the initial phase of perfectly-balanced power-of-two merges
you're left with a cleanup phase in which the merges are not
so well balanced. Sorting a 1025-node list, for example, uses
perfectly-balanced merges to sort the first 1024 items, then
performs a 1024-plus-1 merge to insert the final node: 512.9990+
comparisons (average) to choose among just 1026 possible outcomes.
Inserting another "stage" into McCarthy produces

one list each of 512, 256, ..., 4 nodes
two lists of 2 nodes
one list of 1 node

.... just before the cleanup phase. The cleanup merges are then
2+1, 2+3, 4+5, 8+9, ..., 512+513, each as close to balanced as
an odd number of nodes can be.

 

[Joerg Schoen]

Unbury. "Take alternate entries" just changes the pattern
of splitting (unstably), not the number of split passes. It
makes the same number of node visits (= link traversals) as
"split in the middle" does.

The nice thing about McCarthy's "split mechanism" is that it
makes one count them one pass over the full list instead of the
lg(N) passes of "split in the middle" or "alternate entries."
The resulting sort is stable (assuming you don't do anything dumb).

The un-nice thing about McCarthy's method is that after
the initial phase of perfectly-balanced power-of-two merges
you're left with a cleanup phase in which the merges are not
so well balanced. Sorting a 1025-node list, for example, uses
perfectly-balanced merges to sort the first 1024 items, then
performs a 1024-plus-1 merge to insert the final node: 512.9990+
comparisons (average) to choose among just 1026 possible outcomes.
Inserting another "stage" into McCarthy produces

one list each of 512, 256, ..., 4 nodes
two lists of 2 nodes
one list of 1 node

... just before the cleanup phase. The cleanup merges are then
2+1, 2+3, 4+5, 8+9, ..., 512+513, each as close to balanced as
an odd number of nodes can be.

Sounds interesting, though I don't understand it fully and
I don't have access to any copy of Knuth's books. Code might
be interesting, though. What about posting it or making it
available for download?

If I get it correctly, the algorithm you are talking about
is unstable, works well only for powers of two (except with
some special modification to avoid this) and doesn't
recognize natural runs in the input? I would like to test
it against mine to see how it performs.

 

[Richard Harter]

(e-mail address removed) wrote:

Thanks for the comment! Your implementation is basically the one
from Sedgewick's book. It has the disadvantage that you have to
run through the linked lists repeatedly to split it, but it is
also localized, i.e. takes advantage of caches.

Well, I read Sedgewick long ago . However I fail to see how
you can do a merge without first splitting.

Split and merge as you go. See TAOCP (vol III) exercise
5.2.4-17, where the idea is credited to John McCarthy. The
basic McCarthy method has peaks of inefficiency when the list
length is one greater than a power of two (more generally, when
the binary representation of the node count has 1-bits that are
separated by runs of 0-bits), but I've found[*] a simple way to
fix them without losing much speed in the nicer cases. Code
available on request.

[*] I also "found" McCarthy's method for myself before
reading it in Knuth, and for all I know others have found "my"
improvement before I did. The original is a truly pretty
algorithm, a real "Why didn't I think of that?" piece of work.
Highly recommended!

My Knuth is buried in boxes somewhere. Sounds as if the split
mechanism is something like take alternate entries, and my instinct
tells me that this will disturb the stability of the sort, which in
turn is one of the most attractive features of mergesort.

You're thinking of his algorithm L. He does split the list using
alternate entries. I think you're right about L not being stable,
though there may be some hidden trick in his description. (I really
hate Knuth's algorithm descriptions.) However the McCarthy algorithm is
stable.

 

[Richard Harter]

Sounds interesting, though I don't understand it fully and
I don't have access to any copy of Knuth's books. Code might
be interesting, though. What about posting it or making it
available for download?

If I get it correctly, the algorithm you are talking about
is unstable, works well only for powers of two (except with
some special modification to avoid this) and doesn't
recognize natural runs in the input? I would like to test
it against mine to see how it performs.

You don't get it correctly. You are implementing McCarthy's algorithm.
He's talking about the same thing that you are doing, except that he is
making a slight modification at the end to avoid some final inefficient
merges. His version is stable. Recognizing natural runs in the input
is irrelevant. The basic unit in McCarthy's algorithm is an ascending
run. It can be a run of length 1 or a natural ascending run.