[gclist] Sorting a doubly linked list.

Henry G. Baker hbaker@netcom.com
Tue, 3 Dec 1996 11:56:30 -0800 (PST)

> Charles Fiterman wrote:
> > Does anyone know the best algorithm for sorting a
> > doubly linked list without allocating a lot more
> > storage. I'm only using a doubly linked list because
> > I need to remove items quickly.
> Am I talking non-sense,
> or couldn't you apply a fast sort algorithm
> on an array of pointers to your list elements,
> and only after the order is computed update the list?
> == Fare' -- rideau@ens.fr -- Franc,ois-Rene' Rideau -- DDa(.ng-Vu~ Ba^n ==
> URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"

Good idea.  Copying to a different data structure is typically a good
heuristic if the operation is more than linearly complex -- e.g., nlogn
or n^2.  Thus, sorting and bignum multiplication are good candidates, but
bignum addition is not.

Henry Baker
www/ftp directory: