Why is the minimalist, example Haskell quicksort not a "true" quicksort?
The true quicksort has two beautiful aspects:
- Divide and conquer: break the problem into two smaller problems.
- Partition the elements in-place.
The short Haskell example demonstrates (1), but not (2). How (2) is done may not be obvious if you don't already know the technique!
True inplace quicksort in Haskell:
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Generic.Mutable as M
qsort :: (V.Vector v a, Ord a) => v a -> v a
qsort = V.modify go where
go xs | M.length xs < 2 = return ()
| otherwise = do
p <- M.read xs (M.length xs `div` 2)
j <- M.unstablePartition (< p) xs
let (l, pr) = M.splitAt j xs
k <- M.unstablePartition (== p) pr
go l; go $ M.drop k pr