[gclist] Sorting a doubly linked list.
Henry G. Baker
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' -- firstname.lastname@example.org -- 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.