Date: Wed, 29 Apr 1998 11:38:17 +0300 (IDT)
From: Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>
To: Michel Julier <julier AT clipper DOT ens DOT fr>
cc: djgpp AT delorie DOT com
Subject: Re: Library Function qsort() Exhibits N^2 Behavior
In-Reply-To: <199804290821.KAA06307@drakkar.ens.fr>
Message-ID: <Pine.SUN.3.91.980429113349.1429T-100000@is>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Precedence: bulk


On Wed, 29 Apr 1998, Michel Julier wrote:

> As far as I know it, the QSORT algorithm is "generally" fast, but in
> some special cases, that shouldn't occur often "by chance", it can be
> very slow, indeed N^2.

AFAIK, the DJGPP version handles some of these cases by avoiding the 
quadratic behavior.

> If you are looking for algorithms that are 
> always fast, even in pathological cases, you'll have to look for a
> completely different algorithm, possibly a more complex one or one that
> requires a few extra bytes or memory per item, or maybe that has a larger
> constant factor for the time spent "constant * n * log(n)".

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.

Since DJGPP is run by volunteers on their free time, nothing here gets 
done without interested individual(s) willing to invest their time and 
talent into improving DJGPP.