== Quote from Walter Bright ([email protected])'s article
> qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
> prominently featured in Haskell's official introduction page:
> http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
> Ain't that cool? But look closer. The advantage of quicksort is that it
> is an *in-place* sort. The Haskell one creates new arrays for every
> state in the sort.

I think this can be optimized out in theory, though I have no idea how often it 
is
in practice.

> The other fundamental problem with the Haskell
> version is that it selects the first array element as the "pivot". This
> is the worst choice, since arrays to be sorted tend to already be mostly
> sorted, and quicksort gives quadratic performance to sort an already
> sorted array with the first element as the pivot.

True.  All you'd need to remedy this, though, is a median of 3 function.

Reply via email to