Re: quicksort and compiler optimization

[Ralf Hinze]

> Also it misses a few useful optimizations, such as median-of-three
> partitioning.  For descriptions of that and other ways to speed
> up quicksort, see Sedgewicks "Algorithms in C" or "Algorithms in Pascal"
> (I'm afraid Sedgewick didn't write an "Algorithms in Haskell" ;-).

Median of three more or less assumes that indexing can be done in
constant time which is not the case for the list base variants of
quicksort. Here is another pointer ...

article{BMc93Eng,
    author    = "Bentley, Jon Louis;McIlroy, M. Douglas ",
    title     = "Engineering a Sort Function",
    year      = 1993,
    journal   = "Software --- Practice \& Experience",
    volume    = 23,
    number    = 11,
    pages     = "1249--1265",
    month     = nov
}

The SML library contains an SML version of that code (as far as I
remember).

Ralf