[gclist] Sorting a doubly linked list.

[Henry G. Baker]

> 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.)

-- 
Henry Baker
www/ftp directory:
ftp.netcom.com:/pub/hb/hbaker/home.html