To: OCAML <email@example.com>
Subject: Re: Sort.array easily degenerates
In-Reply-To: Message of Tue, 9 Mar 1999 11:44:42 +0100
from Xavier Leroy <Xavier.Leroy@inria.fr>
Date: Tue, 09 Mar 1999 15:03:05 -0800
>From: Xavier Leroy <Xavier.Leroy@inria.fr>
>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
Also, you should recurse on the smallest subarray first, not the
I vote for Shellsort.
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:20 MET