Re: list strawman

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

dennison@telepath.com (Ted Dennison) writes:

> Jean-Marc Bourguet <jm@bourguet.org> wrote in message
> news:<7uir1a.s11.ln@192.168.0.2>...
> > What I presented is algorithm L in section 5.2.4 of The Art Of
> > Computer Programming (in the third volume) modified according
> > exercise 12 of the same section.  All the ideas are also presented
> > in the section 5.4 of the same book. I don't think I'll get a
> > prize for reading Knuth and his solutions to his exercises :-)
> 
> You probably should. Not enough people do that. :-)
> 
> I wish I had a copy myself. Its been on my Xmas book list for 3
> years running, but no-one seems to want to buy me a $50 book on
> algorithms (much less a set of 3 of them). :-(

I did the same,... and ended by bying them myself :-)
 
> > More precisely, what I wrote was supposed to be that. Reading
> > Knuth anew I see one bug which modify the number of operations
> > needed to be O(N^2) on average.
> ...
> > Appended is a fixed version with a test harness.
> 
> I'm still not convinced that you have a mergesort solution here that
> is O(n) for sorted lists, as was advertised.

For sorted list, Merge is never run.  And Split is O(n).

-- 
Jean-Marc