On Mon, Jan 01, 2001 at 02:04:25PM -0600, Jonathan Scott Duff wrote:
> On Fri, Dec 29, 2000 at 11:47:59PM -0600, Jarkko Hietaniemi wrote:
> > The sorting algorithm? Before 5.005 (I think...my memory is going)
> > vendors' quicksort, after that Tom Horsley's excellent ultratuned
> > quicksort (since vendors' quicksorts were (a) buggy (c) slow),
> > in 5.7 mergesort by John Lindermann was introduced.
>
> Could someone give me a pointer to the whys and wherefors of the
> change from quicksort to mergesort?
Executive summary:
(1) Quicksort has a weak point where it goes deep into the Quadratic Land:
(nearly) already ordered data. No, that is not so far-fetched a case.
Mergesort has no similar weakpoints: its performance is in fact
consistently N log N.
(2) Mergesort is stable. Quicksort is not.
Some of the discussion:
http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2000-09/msg00484.html
(and the following thread)
and a real-life case:
http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2000-12/msg00241.html
http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2000-12/msg00244.html
> thanks,
>
> -Scott
> --
> Jonathan Scott Duff
> [EMAIL PROTECTED]
--
$jhi++; # http://www.iki.fi/jhi/
# There is this special biologist word we use for 'stable'.
# It is 'dead'. -- Jack Cohen
