[gclist] Sorting a doubly linked list.

[Henry G. Baker]

> 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:
ftp.netcom.com:/pub/hb/hbaker/home.html