From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,cda33fc7f63c2885
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-01-14 08:02:50 PST
Path: archiver1.google.com!postnews1.google.com!not-for-mail
From: dennison@telepath.com (Ted Dennison)
Newsgroups: comp.lang.ada
Subject: Re: list strawman
Date: 14 Jan 2002 08:02:50 -0800
Organization: http://groups.google.com/
Message-ID: <4519e058.0201140802.678399db@posting.google.com>
References: <mailman.1010451062.16465.comp.lang.ada@ada.eu.org>
 <7iE_7.8661$cD4.15714@www.newsranger.com>
 <3c3b13ba$0$212$626a54ce@news.free.fr>
 <sHF_7.8807$cD4.16831@www.newsranger.com>
 <3c3b2aa0$0$212$626a54ce@news.free.fr>
 <zwH_7.9026$cD4.17983@www.newsranger.com>
 <3c3bfabc$0$3190$626a54ce@news.free.fr>
 <4519e058.0201091037.325fbdbb@posting.google.com>
 <3c3eb272$0$282$626a54ce@news.free.fr> <3C3F1A0F.2000706@telepath.com>
 <7uir1a.s11.ln@192.168.0.2>
NNTP-Posting-Host: 65.115.221.98
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1011024170 11005 127.0.0.1 (14 Jan 2002 16:02:50
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 14 Jan 2002 16:02:50 GMT
Xref: archiver1.google.com comp.lang.ada:18909
Date: 2002-01-14T16:02:50+00:00
List-Id: <comp.lang.ada>

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.