Sorting Double Linked List in place

[Dan Bernstein]

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).
  [ .. ]
> Knuth doesn't seem to help on this one>

Everything that Knuth says about tape sorting is directly applicable
here. You have a bit more freedom in memory use, but you won't find a
noticeably more efficient algorithm.

---Dan