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-02 11:59:04 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.icl.net!newsfeed.fjserv.net!newsfeed.freenet.de!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!news.belwue.de!news.uni-stuttgart.de!not-for-mail
From: Florian Weimer <Weimer@CERT.Uni-Stuttgart.DE>
Newsgroups: comp.lang.ada
Subject: Re: Smart sorting algorithm ?
Date: Tue, 02 Jul 2002 20:57:34 +0200
Organization: Comp.Center (RUS), U of Stuttgart, FRG
Message-ID: <87lm8u3qld.fsf@CERT.Uni-Stuttgart.DE>
References: <3D21D581.6EF6CB06@despammed.com>
NNTP-Posting-Host: login.cert.uni-stuttgart.de
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: news.uni-stuttgart.de 1025636344 12854 129.69.16.19 (2 Jul 2002
 18:59:04 GMT)
X-Complaints-To: news@news.uni-stuttgart.de
NNTP-Posting-Date: Tue, 2 Jul 2002 18:59:04 +0000 (UTC)
User-Agent: Gnus/5.090007 (Oort Gnus v0.07) Emacs/21.2
 (i386-debian-linux-gnu)
Cancel-Lock: sha1:X3VwJfSLDgvqpIuhixKXc2KZ4aM=
Xref: archiver1.google.com comp.lang.ada:26813
Date: 2002-07-02T20:57:34+02:00
List-Id: <comp.lang.ada>

Wes Groleau <wesgroleau@despammed.com> writes:

> The reason I'm asking is that I have a situation
> where deciding the order of two items is very slow.

Try insertion sort with a binary search.  Still O(n^2) operations in
total, but only about log_2 n! comparisons.