Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!cbmnlux!cbmehq!cbmvie!alison!mjl
From: mjl@alison.at (Martin J. Laubach)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Message-ID: <mjl.8698@alison.at>
Date: 8 May 91 17:16:41 GMT
References: <1193@cbmger.UUCP> <1991May3.201243.7959@watdragon.waterloo.edu>
 <1991May6.155148.1201@zorch.SF-Bay.ORG> <MWM.91May7111453@raven.pa.dec.com>
Reply-To: mjl@alison.at
Organization: The Austrian Amiga Developers Association/ETA002
Lines: 16

| In article <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes:
|    While it does (barely) beat heapsort, it takes almost twice as long
|    as quicksort

  Pardon me -- I don't want to start a "my sort is better than your sort"
thread, I just want to find out whether the stuff we learnt is correct
or not...

  Following my docs, heapsort always does O(N ld N), while quicksort
is N ld N (best), N^2/2 (worst case), and 1.4 N ld N (average).

  Doesn't this mean that heap and quick are about the same, but the
possibility of an anomaly in quicksort?


	mjl