Sorting Double Linked List in place

[Doug Gwyn]

In article <1990Nov7.160701.5838 at bkj386.uucp> anton at analsyn.UUCP (PUT YOUR NAME HERE) 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.  

Heck, that's easy.  You need one extra dummy "header" node.
Walk the original list, unlinking each node and inserting it into a
binary search tree rooted at the auxiliary header node.
Then traverse the binary search tree, rotating nodes to unbalance it,
eventually putting every node in a single path.
Finally, walk the (now singly-linked) list, recreating the reverse links.