Re: Sort.array easily degenerates

Date: Wed Mar 10 1999 - 00:03:05 MET

Message-Id: <>
To: OCAML <>
Subject: Re: Sort.array easily degenerates
In-Reply-To: Message of Tue, 9 Mar 1999 11:44:42 +0100
    from Xavier Leroy <>
Date: Tue, 09 Mar 1999 15:03:05 -0800

>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

I vote for Shellsort.

-- Damien

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