Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!sdd.hp.com!uakari.primate.wisc.edu!aplcen!haven!adm!smoke!gwyn
From: gwyn@smoke.brl.mil (Doug Gwyn)
Newsgroups: comp.lang.c
Subject: Re: Sorting Double Linked List in place
Message-ID: <14403@smoke.brl.mil>
Date: 9 Nov 90 07:26:39 GMT
References: <1990Nov7.160701.5838@bkj386.uucp>
Organization: U.S. Army Ballistic Research Laboratory, APG, MD.
Lines: 14

In article <1990Nov7.160701.5838@bkj386.uucp> anton@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.