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,385be4c68a9e4de6
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-07-08 21:35:48 PST
Path: archiver1.google.com!postnews1.google.com!not-for-mail
From: dewar@gnat.com (Robert Dewar)
Newsgroups: comp.lang.ada
Subject: Re: Smart sorting algorithm ?
Date: 8 Jul 2002 21:35:47 -0700
Organization: http://groups.google.com/
Message-ID: <5ee5b646.0207082035.65f948ce@posting.google.com>
References: <3D21D581.6EF6CB06@despammed.com>
 <3D2A0A25.52A62B7C@despammed.com>
NNTP-Posting-Host: 205.232.38.246
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1026189348 22139 127.0.0.1 (9 Jul 2002 04:35:48
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 9 Jul 2002 04:35:48 GMT
Xref: archiver1.google.com comp.lang.ada:26958
Date: 2002-07-09T04:35:48+00:00
List-Id: <comp.lang.ada>

Wes Groleau <wesgroleau@despammed.com> wrote in message news:<3D2A0A25.52A62B7C@despammed.com>...
> > Anyone know anything about a sorting algorithm
> > that includes the ability to infer the answer
> > to a comparison from comparisons already done?
> 
> I solved this part.  Wrote an "<" that
> first checks a 2D lookup table.  If the 
> answer is "unknown" it does the comparison,
> then updates as many cells in the table as
> possible.  Once you compare A & B, you may
> be able to determine (and record) the
> order of A,C based on B,C or vice versa.

That's just got to be a non-optimal solution. You just
can't get below NlogN comparisons this way, so why not
just use a decent NlogN comparison algorithm in the first
place (e.g. GNAT.Heap_Sort_A). I think you are wasting
your time here.