Re: list strawman

[Ted Dennison<dennison@telepath.com>]

In article <3c3b2aa0$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says...
>
>I'm sorry, I was thinking about heap sort.

Ahh. Yeah, heapsort would probably be a bad idea in this package. In a *.Maps
package it might make sense, if things are already kept in a heap anyway. 

>Yes.  There is still the problem of choosing the pivot.  With random
>access, I'd use a random element.  Without random access, you'll have
>to choose the first or the last element and then degenerate in N^2 for
>a sorted input, not something I'd like in a general purpose library.

That's a good point. It would probably be fairly easy to alternate which side
the pivot is taken from. Then again, I think the advice to use a different
package if sorting is *really* important to you should mitagate this issue.
Also, we provide tools to insert into a pre-sorted list, so the only reason
anyone should ever hit the worst case is ignorance or really bad luck.

>Well, I think I'd still choose a merge sort.

I believe the splitting part of mergesort would involve a linear search for a
linked-list. That would take us into O(n*2) territory, if not worse. In my
student days I could figure out the exact factor...hmmm...perhaps its just
another nlogn...

Despite taking Computer Science Algorithms courses no less than 3 times (or
perhaps *because* I had to :-) ), I'm not really a sorting expert. But all the
literature I read highly suggests one use Quicksort, despite its theoretical
O(n**2) behavior. http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html is
a good example. 

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