# [gclist] Sorting a doubly linked list.

**Henry G. Baker**
hbaker@netcom.com

*Tue, 3 Dec 1996 15:29:29 -0800 (PST)*

>* At 12:01 PM 12/3/96 -0800, you wrote:
*>* >> 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
*>*
*>* Oh come on Henry. So you have the list [1,2,3,4 ... 1000]. So you take
*>* the 1 off the head and produce three lists [] 1 and [2,3,4,5 ... 1000] and
*>* you take the third list and get [] 2 and [3,4,5,6 ... 1000] great algorithm
*>* Knuth would be proud.
*
I'm having a hard time concluding from Strandh's posting quoted above
exactly how the pivot element is chosen. So I don't understand how you
can conclude that such a choice would necessarily be inefficient.
I was merely responding to the overall structure of the algorithm, not
the choice of 'pivot' elements.
--
Henry Baker
www/ftp directory:
ftp.netcom.com:/pub/hb/hbaker/home.html