Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
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: Xavier Leroy <Xavier.Leroy@i...>
Subject: Re: Sort.array easily degenerates
> 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