[gclist] Sorting a doubly linked list.

[Charles Fiterman]

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 wrote the array qsort in Coherent and won every benchmark three years ago.
Start with the middle element as a pivot. If there is order this is the
best guess and if there is no order it doesn't matter. If its a bad choice,
I used (small partition < large partation/8) means a bad pivot, try 1/4 of
the way in. If thats a bad choice try 1/8 if thats bad go to shellsort.
With arrays expanding the center list turned out worse.

How good was it? One benchmark was an array 1 ... 10000 1 ... 10000 it was
called merging decks. My qsort took three seconds some of the others took
twelve hours. I can't have a garbage collector take twelve hours to sort
finalizers. This is why Knuth suggested random pivots.


Charles Fiterman	Geodesic Systems
Phone 312-728-7196	4745 N. Ravenswood Suite 111
Fax   312-728-6096	Chicago Il 60015
cef@geodesic.com

A computer language without garbage collection
  is like a city without garbage collection.