[gclist] Sorting a doubly linked list.

Henry G. Baker hbaker@netcom.com
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
> cef@geodesic.com

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.

Henry Baker
www/ftp directory: