Re: list strawman

[dennison@telepath.com (Ted Dennison)]

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). :-(

> 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. I'll have to study it
pretty hard to be sure though (and I'm not sure I care to do that, as
I already have a working implementation of Quicksort going). It
doesn't really look like a mergesort implementation the way I'm used
to thinking of them, as there is no recursion, and only one call to
Split. Split also seems to be doing some sorting work.