[gclist] Sorting a doubly linked list.

[wru@access.digex.net]

> Does anyone know the best algorithm for sorting a
> doubly linked list without allocating a lot more
> storage. I'm only using a doubly linked list because
> I need to remove items quickly.

Merge sort algorithms are efficient and convenient for linked lists.

Use a modest fixed size stack of anchors to keep track of zero or one
string of lengths 1, 2, 4, 8, 16, ....

Merge a pair of strings of length 1 to get a string of length 2
Merge a second pair of length 1 to get a second string of length 2
Merge those to get a string of length 4
Repeat to get a second string of length 4
Merge them to get a string of length 8
Repeat to get a second string of length 8
Merge....
etc.

The same merge pattern will work with "runs" taken from the input.

An algorithm something like this was published in the old
CACM Algorithms column, probably in the early 1970's. My recollection
is that the author was Dutch and associated with T.H.E.


William Rutiser
APL2000, Inc.
wru@apl2000.com
William A. Rutiser       APL2000, Inc.
301-998-8801             wru@apl2000.com