Why is the minimalist, example Haskell quicksort not a "true" quicksort?

The true quicksort has two beautiful aspects:

  1. Divide and conquer: break the problem into two smaller problems.
  2. 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