Mime-Version:	1.0
To:	Francois Charton <deef AT pobox DOT oleane DOT com>,
	Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>
From:	Nate Eldredge <nate AT cartsys DOT com>
Subject:	Re: Heapsort [was: Library Function qsort() Exhibits N^2
	Behavior]
Cc:	djgpp AT delorie DOT com
Date:	Wed, 29 Apr 1998 15:47:12 -0700
Message-ID:	<19980429224701.AAC11144@ppp123.cartsys.com>

At 12:37  4/29/1998 +0200, Francois Charton wrote:
>Eli Zaretskii wrote:
>> 
>> If somebody has a better implementation of `qsort' which is free (not
>> GPL/LGPL), please point to it.  Failing that, we will need to wait until
>> somebody becomes so annoyed by the current implementation that he/she
>> actually sits down, corrects it, and submits the patches to DJ Delorie.
>> 
>
>For those who do not want to run the (very small) risk of one of 
>these N^2 cases (when qsort() becomes very slow) happening, an 
>alternative algorithm which always exhibits O(n log(n)) behaviour is 
>heapsort. 

Here's another $0.02, despite the fact that I know very little about sorting
algorithms:

The GNU C library uses an algorithm called mergesort, which as far as I have
been able to gather is faster than either, though it requires some memory
overhead.

Incidentally, aren't there some adjustments you can make to quicksort to
eliminate the worst-case behavior?

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.

Nate Eldredge
nate AT cartsys DOT com

- Raw text -