Re: Sort.array easily degenerates

From: Xavier Leroy (Xavier.Leroy@inria.fr)
Date: Tue Mar 09 1999 - 11:44:42 MET


Date: Tue, 9 Mar 1999 11:44:42 +0100
From: Xavier Leroy <Xavier.Leroy@inria.fr>
To: Markus Mottl <mottl@miss.wu-wien.ac.at>, OCAML <caml-list@inria.fr>
Subject: Re: Sort.array easily degenerates
In-Reply-To: <199903060027.BAA03901@miss.wu-wien.ac.at>; from Markus Mottl on Sat, Mar 06, 1999 at 01:27:29AM +0100

> I have played around with the new functions and modules in the new
> OCAML-release. Besides other things I have tested the new function for
> sorting arrays (Sort.array).
> I am not sure where the problem in the implementation is, but the
> "qsort"-function, which is applied in "Sort.array" degenerates easily
> on pre-sorted and/or non-unique data.

The Sort.array implementation is Quicksort with insertion sort for
small partitions, as suggested in Sedgewick. I should know better
than take some code out of an algorithms textbook and expect that it
will work well...

At any rate, any one is welcome to send me a better implementation.

- Xavier Leroy



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:20 MET