Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: Sort.array easily degenerates
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: doligez@p...
Subject: Re: Sort.array easily degenerates

>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
Sedgewick's pseudo-code.

Also, you should recurse on the smallest subarray first, not the
largest.


I vote for Shellsort.

-- Damien