From: Paul Shirley <Paul AT chocolat DOT obvious DOT fake DOT foobar DOT co DOT uk>
Newsgroups: comp.os.msdos.djgpp
Subject: Heapsort [was: Library Function qsort() Exhibits N^2 Behavior]
Date: Thu, 30 Apr 1998 13:47:54 +0100
Organization: wot? me?
Message-ID: <1og7pGA6LHS1Ewpf@foobar.co.uk>
References: <19980429224701 DOT AAC11144 AT ppp123 DOT cartsys DOT com>
NNTP-Posting-Host: chocolat.foobar.co.uk
Mime-Version: 1.0
Lines: 14
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

In article <19980429224701 DOT AAC11144 AT ppp123 DOT cartsys DOT com>, Nate Eldredge
<nate AT cartsys DOT com> writes
>Another point is that anybody who *really* cares about the speed of their
>sort shouldn't be using `qsort' anyway, but their own algorithm which takes
>their application into account.

Thats what puzzled me, the N^2 behaviour of QuickSort and some other
fast sorts is well known and being surprised that qsort() shows it is
naive. I've *never* seen an example of realtime software that uses
qsort() because its worst case behaviour is unpredictable, in fact I've
seen comb sort used more than anything else (because AFAIK it has no
pathological behaviours).
---
Paul Shirley: my email address is 'obvious'ly anti-spammed