[gclist] Sorting a doubly linked list.

Henry G. Baker hbaker@netcom.com
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.)

Henry Baker
www/ftp directory: