[gclist] Sorting a doubly linked list.

[Charles Fiterman]

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.

I know qsort is bogus because it takes an explosive
amount of time with sorted data or all keys the 
same and these are my most likely cases.

I'm starting to think I need to keep a heapsort
type heap but this involves keeping a parent pointer.

Bubblesort (yuchh yuchh) is starting to look good. 
This is because of two added complications. One I
must run the sort in little increments and give 
control back to other processes. Second those
processes may remove from but not add to my list.
Third sorted data and all keys the same are likely
to be the most typical cases.

Is there a similar email group for computer science?
I mean the kind of thing Knuth does. Does anyone have 
a list of computer email groups?

Charles Fiterman	Geodesic Systems
Phone 312-728-7196	4745 N. Ravenswood Suite 111
Fax   312-728-6096	Chicago Il 60015
cef@geodesic.com

A computer language without garbage collection
  is like a city without garbage collection.