{-# LANGUAGE BangPatterns, ScopedTypeVariables #-}
module Main where
import           Control.Monad.Primitive
import           Control.Applicative ((<$>))
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as M

partition :: (PrimMonad m, Ord a, M.Unbox a) => Int -> M.MVector (PrimState m) a -> m Int
partition !pi !v = do
    pv <- M.unsafeRead v pi
    M.unsafeSwap v pi lastIdx
    pi' <- go pv 0 0
    M.unsafeSwap v pi' lastIdx
    return pi'
  where
    !lastIdx = M.length v - 1

    go !pv i !si | i < lastIdx =
       do iv <- M.unsafeRead v i
          if iv < pv
            then M.unsafeSwap v i si >> go pv (i+1) (si+1)
            else go pv (i+1) si
    go _   _ !si                = return si

qsort :: (PrimMonad m, Ord a, M.Unbox a) => M.MVector (PrimState m) a -> m ()
qsort v | M.length v < 2 = return ()
qsort v                    = do
    let !pi = M.length v `div` 2
    pi' <- partition pi v
    qsort (M.unsafeSlice 0 pi' v)
    qsort (M.unsafeSlice (pi'+1) (M.length v - (pi'+1)) v)