[gclist] Sorting a doubly linked list.

[Robert STRANDH]

> 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.

I am no expert in sorting algorithms, but I think that the reason
qsort takes a lot of time if the data is sorted, is that you normally
use the first element as a pivot.  You can fix this either by
calculating the median element, or if you think your list is mostly
sorted, take the middle element. 

For the second problem, I don't think there is one.  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

---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------