[gclist] Sorting a doubly linked list.
Henry G. Baker
Tue, 3 Dec 1996 12:01:15 -0800 (PST)
> You simply split
> your data into three categories, less, equal, and greater than the
> pivot. You only sort the ones that are less and greater. Then you
> append the three resulting lists. When all keys are the same, the
> pivot is necessarily one of those. All elements will thus be in the
> `equal' caterogy, thus not sorted.
> Robert Strandh
This is the 'list' version of quicksort. See
ftp://ftp.netcom.com/pub/hb/hbaker/LQsort.html (also .ps.Z)
for both list and array quicksorts.
(Of course, _doubly_ linked lists are no longer 'linear', but they can
still be handled in 'linear'-like ways -- e.g., via exchanges and rotatef's.)