[gclist] Sorting a doubly linked list.

[Darius Blasband]

> 
> 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.
> 

We use a sorb:

Basically, you truncate your input into sorted sublists.
(quite simple, and efficient if your list is already sorted)

Each of these sorted sublists is then entered into a logarithmic
pool (an small (32) array of list entries): the first list is stored 
in the first entry of the pool, the second cannot be stored in this
entry since it is now used, so it is merged with the first entry,
and the resulting sublist is stored in the second entry of the pool,
unless it is used already, in which case merge occurs again...

I can send you the full source in Modula II or in YAFL, because when
I read the description above, I am not specially proud of myself...

In any way, sorb has nice properties:

- It is stable if the list is already sorted
- It has a nlogn worse case complexity.

Do you think you can use this, or am I entirely wrong ?

Cheers,

darius