Re: list strawman

[Jean-Marc Bourguet <jm@bourguet.org>]

Ted Dennison<dennison@telepath.com> writes:

> In article <3c3b2aa0$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says...

[...]

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

This will not change the behaviour in N^2 for a (nearly) sorted input.

[...]

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

Merge sort can be implemented in O(N log N) worst case, with a O(N)
for an already sorted input.
 
> 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.

Most litterature I've read is about sorting arrays.  AFAIK, it is not
possible to do merge sort in place for arrays (but it is for linked
list, even singly linked list) and that's probably why this algorithm
is often neglected.

Yours,

-- 
Jean-Marc