[gclist] Sorting a doubly linked list.

[Henry G. Baker]

> 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