Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
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>
Precedence: bulk

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