[gclist] Sorting a doubly linked list.

Charles Fiterman cef@geode.geodesic.com
Wed, 04 Dec 1996 08:29:28 +0000

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

Sorry about that then but list forms of qsort traditionally choose
the first element for a pivot. I laugh every time I see this drivel
propagated in textbooks. It shows qsort as the most efficient of sorts
with an implementation that ends up running in exponential time on
presorted data.

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

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