Re: list strawman

[Ted Dennison<dennison@telepath.com>]

In article <a1fo5f$o10$1@a1-hrz.uni-duisburg.de>, Georg Bauhaus says...
>
>Another suggestion: Saving the current length of the list will allow
>a quick inspection to choose an algorithm, so Insertion Sort could be
>used for short lists, which can be made stable and is faster for doubly
>linked lists than for arrays. 
>Also, it does not have the n**2 problem for pre-sorted lists.

We probably don't want to get into the business of specifying implementations.
It may be reasonable to say things like "sort should be O(nlogn) in the average
case.", or "sort shall be stable", or even "Size should be O(C) in the worst
case". But I think what sort algorithm to use should be almost entirely left up
to the discretion of the implementors.

Now you might have meant this as a suggestion to us implementors. For my
reference implementation, I'm planning on just using a relatively simple
Quicksort (hopefully in-place, non-recursive, and stable). I don't care that
much about efficiency for small lists because the Sort is going to be quick on
small lists anyway, so there isn't all that much time to gain. Its not really
worth undully complicating things for them. I also don't really think its worth
pouring mass quantities of effort into making this sort as fast as possible,
since "*.Maps.Unbounded.Map" will presumably be the place to turn when you want
to deal with a sorted structure. 

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.