From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA18098 for caml-redistribution; Tue, 9 Mar 1999 13:34:04 +0100 (MET)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA01158 for <caml-list@pauillac.inria.fr>; Tue, 9 Mar 1999 11:44:46 +0100 (MET)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id LAA14147;
	Tue, 9 Mar 1999 11:44:41 +0100 (MET)
Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA25823; Tue, 9 Mar 1999 11:44:42 +0100 (MET)
Message-ID: <19990309114442.07231@pauillac.inria.fr>
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
References: <199903060027.BAA03901@miss.wu-wien.ac.at>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 0.89.1
In-Reply-To: <199903060027.BAA03901@miss.wu-wien.ac.at>; from Markus Mottl on Sat, Mar 06, 1999 at 01:27:29AM +0100
Sender: weis

> 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