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 KAA14321 for caml-redistribution; Wed, 10 Mar 1999 10:23:03 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id AAA29309 for ; Wed, 10 Mar 1999 00:03:08 +0100 (MET) Received: from mail2.digital.com (mail2.digital.com [204.123.2.56]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id AAA03444 for ; Wed, 10 Mar 1999 00:03:06 +0100 (MET) From: doligez@pa.dec.com Received: from six.pa.dec.com (six.pa.dec.com [16.4.80.66]) by mail2.digital.com (8.9.2/8.9.2/WV2.0e) with SMTP id PAA00948 for ; Tue, 9 Mar 1999 15:03:06 -0800 (PST) Received: by six.pa.dec.com; id AA14481; Tue, 9 Mar 1999 15:03:05 -0800 Message-Id: <199903092303.AA14481@six.pa.dec.com> To: OCAML Subject: Re: Sort.array easily degenerates In-Reply-To: Message of Tue, 9 Mar 1999 11:44:42 +0100 from Xavier Leroy <19990309114442.07231@pauillac.inria.fr> Date: Tue, 09 Mar 1999 15:03:05 -0800 X-Mts: smtp Sender: weis >From: Xavier Leroy >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... There's no way to implement Sedgewick's quicksort with the interface given in sort.mli. You'd need two comparison functions, one for ">=" and one for "<=". That explains the degenerate case when all the elements are equal. And it degenerates on already-sorted data because you swap the pivot with the right-most element. As a consequence, one of the subarrays has its two highest elements in first and last positions, which makes the median-of-three degenerate. I think this bug is also in Sedgewick's pseudo-code. Also, you should recurse on the smallest subarray first, not the largest. I vote for Shellsort. -- Damien