[gclist] Sorting a doubly linked list.
Henry G. Baker
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.