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 13:48:40 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!kibo.news.demon.net!demon!newsfeed.stueberl.de!uucp.gnuu.de!newsfeed.arcor-online.net!news.belwue.de!cert.uni-stuttgart.de!news.enyo.de!not-for-mail
From: Florian Weimer <fw@deneb.enyo.de>
Newsgroups: comp.lang.ada
Subject: Re: Smart sorting algorithm ?
Date: Tue, 02 Jul 2002 22:48:40 +0200
Organization: Enyo -- not your organization
Message-ID: <8765zxx3dj.fsf@deneb.enyo.de>
References: <3D21D581.6EF6CB06@despammed.com>
 <3D21DC25.AD402F70@easystreet.com>
NNTP-Posting-Host: deneb.enyo.de
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: cygnus.enyo.de 1025642912 4935 212.9.189.171 (2 Jul 2002 20:48:32
 GMT)
X-Complaints-To: abuse@enyo.de
NNTP-Posting-Date: 2 Jul 2002 20:48:32 GMT
Cancel-Lock: sha1:UiyQUullIiNMLeCdarlXZpsLXnc=
Xref: archiver1.google.com comp.lang.ada:26823
Date: 2002-07-02T20:48:32+00:00
List-Id: <comp.lang.ada>

achrist@easystreet.com writes:

> Using, e.g., qsort, isn't it true that this should not happen?  If
> you've compared A vs B and B vs C, then B is the pivot, and A and C
> are on opposite sides of the pivot and won't get compared.   

Quicksort performs quite a lot of comparisons (for an O(n log n)
algorithm, of course).  It gains its speed from the tightness of its
inner loop, not from saving comparisons.