== 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.
