[gclist] Sorting a doubly linked list.

[Charles Fiterman]

At 10:24 AM 12/3/96 -0500, you wrote:
>> I know qsort is bogus because it takes an explosive
>> amount of time with sorted data or all keys the 
>> same and these are my most likely cases.
>
>There are minor variatious on qsort which make it reasonable for
>those cases.  See the 4.4BSD qsort for working code.

Will do. My minor variation which was in Mark William's Coherent
and won all the benchmarks at the time was as follows.

Take the center element as the first pivot. This is logical
because if there is order the center element makes a great
first pivot and if there is no order it doesn't matter. If
thats a bad choice (small partition < 1/8 large partition)
try 1/4 of the way in, then 1/8. If you have a good choice
go back to 1/2. After 1/8 go to shellsort on that partition.
This is logical because if qsort keeps looking bad there
may be a lot of identical keys and shellsort is the best
sort in this case.

But all this depends on sorting an array where you can say
lets go 1/2 in etc efficiently. I'm trying to sort a list.
If this is in their qsort it assumes an array.

>If you like heapsort, 4.4 has one of those, too.

I'm trying to avoid tree looking things because my data
structure must support quick removal of random elements
and tree looking things will at the least need a parent
pointer to do that.

BTW when I say I won the benchmarks on one test there
was a merging deck problem the data went 1 to 10000
and 1 to 10000 again. Mine took about 3 seconds most
of the others ran 12 hours or so. I can't have an
algorithm that could take 12 hours in a garbage collector.

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.