Sorting Double Linked List in place

[Geoff Rehmet]

In <1990Nov7.160701.5838 at bkj386.uucp> anton at bkj386.uucp (Anton Aylward) 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).

You can use a quicksort on a linked list (doubly or singly linked). 
All you need to do use the head element as the comparator.  This isn't
necessarily the best choice of comparator - especially if your list is
already sorted, or in inverse order!

What you need to do (I'm too lazy to write out a proper algorithm) is
split the list into 2 sublists, one of which contains only elements
greater than the comparator, and the other containing elements less than
or equal to the comparator.
Then recursively sort the 2 sublists and join the lot together with the
comparator in the middle.

You can fix up the backward links of the DLL afterwards - keeping them
consistent during the sort is more work than it's worth.

I hope this helps.

Cheers, Geoff.

-- 
Geoff Rehmet       |      Internet: csgr.quagga at f4.n494.z5.fidonet.org          
Rhodes University  |                csgr at quagga.ru.ac.za (soon - I hope)     
Grahamstown        |      UUCP    : ..uunet!m2xenix!quagga!csgr
-------------------+      Uninet  : csgr at quagga