[gclist] Sorting a doubly linked list.
Henry G. Baker
Wed, 4 Dec 1996 08:56:59 -0800 (PST)
> 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
With a doubly linked list, one can trivially obtain the mean of the first
and last element, which is an optimization very often used on quicksort.