[MLton-user] Re: RFC: Extended Basis Library

[Vesa Karvonen]

On 3/4/07, Scott Cruzen <sic at lerp.com> wrote:
> > for the sorting function that is as fast as possible while being stable
> > (O(n log n) and preserves relative order of equal elements).
[...]
> This is a fast stable qsort
> http://lerp.com/~sic/sml/qsort.sml.html

Hmm...  Fast it may be, but are you sure that it is stable?  The first
section of the article

  http://citeseer.ist.psu.edu/bentley93engineering.html

says that stability isn't a requirement.  The partitioning stage of qsort
is typically unstable.  For unstable sorting, introsort

  http://en.wikipedia.org/wiki/Introsort

seems preferable to other qsort variations as it guarantees O(n lg n) time
complexity with only a small cost.

-Vesa Karvonen