Sorting Double Linked List in place

[Paul N. Hilfinger]

In article <1990Nov7.160701.5838 at bkj386.uucp> anton at analsyn.UUCP writes:
>I'm looking for a routine to sort a double linked list in place, 
>given the head of the list and a compare function for the elements 
>(sort of like qsort).
>
>I've seen single link sorts that use auxillary 'bins" (kind of like 
>merge tape sort), but I'm convinced ther is something more efficient 
>for the DLL, since there is the extra link.  
>

Please forgive a slight engineering quibble here: Given a list of N
elements, you need only lg(N) list heads for those bins, which means
that if you can spare an extra 32 pointer-sized words of storage, you
can sort up to 4,000,000,000 elements.  Of course, if you have room
for that many elements, the reasonable reader might ask why you
quibble about 128 bytes more!

I advise you to use one of those single-link sorts you mentioned.
Assuming it is a form of merge sort, you might just as well ignore the
second links altogether until the very end; they'll just slow you
down.  On the other hand, if you have only a few 10's of elements to
sort, it doesn't matter what you do.

Paul Hilfinger