sorting doubly linked list

[Richard A. O'Keefe]

In article <1991May14.112315.496 at klaava.Helsinki.FI>, wirzeniu at kruuna.Helsinki.FI (Lars Wirzenius) writes:
> In article <OLSON.91May13142102 at sol.aaet.csc.ti.com> olson at aaet.csc.ti.com (Doug Olson) writes:
> >I need an efficient method of sorting these lists based on the key
> >field. Any help would be greatly appreciated.
> 
> How about using a quicksort, ie. (in pseudocode):

There are several ways of approaching this problem.
The one which will get you off the ground fastest is
    -- determine the length of the list
    -- allocate a scratch array holding that many pointers
    -- for (i = 0, p = list; p != NULL; i++, p = p->next)
	a[i] = p;	/* i.e. copy the list pointers into the array */
    -- USE THE STANDARD LIBRARY FUNCTION qsort to sort the array
    -- rebuild the list from the array.
    -- release the scratch array
All of this is trivial.

If for some reason you do not want to allocate a scratch array,
or if you need a really efficient sorting algorithm,

	USE MERGE SORT.

Do *not* use quicksort.  The only advantage of quicksort is that it
doesn't need additional workspace, and when you _have_ a linked list
you already have all the workspace you need.  What is more, quicksort
pays for its space saving by being quite noticably *SLOWER* than
merge sort.

Look in any respected algorithms text (Sedgewick, Rivest et al, ...)
to find out how merge sort works.  Merge sort on one way linked lists
is very very simple and rather fast.  To merge sort two way linked lists,
ignore the back links, then rebuild them after you have finished sorting.

Doubly linked lists are seldom needed; what is the task the original
poster is _really_ interested in?
-- 
There is no such thing as a balanced ecology; ecosystems are chaotic.