Cacher is the code snippet organizer for pro developers

{-# LANGUAGE ScopedTypeVariables #-}
module QuickSort where

import           Control.Monad
import           Control.Monad.Primitive
import           Criterion
import           Criterion.Main
import           Data.List
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as MV
import           Data.Vector.Unboxed         hiding (filter, forM_, head,
                                              reverse, tail, (++))
import qualified Data.Vector.Unboxed.Mutable as M
import           Test.QuickCheck
import           Test.QuickCheck.Instances

qs :: Ord a => [a] -> [a]
qs [] = []
qs (x:xs) = qs left ++ [x] ++ qs right
  where
     left  = filter (<x) xs
     right = filter (>=x) xs

quickSort :: Vector Int -> Vector Int
quickSort = modify f
  where
    f :: (Ord a, PrimMonad m, Unbox a) => MVector (PrimState m) a -> m ()
    f v = qsort v 0 (M.length v - 1)
      where
        qsort a low high =
          when (low < high) $ do
            p <- partition a low high
            qsort a low (p - 1)
            qsort a (p + 1) high

        partition a low high = do
          pivot <- M.read a high
          go low (high-1) low pivot a

        go l h i pivot a =
          if l <= h
            then do
               aj <- M.read a l
               if aj <= pivot
                 then do
                   M.swap a l i
                   go (l+1) h (i+1) pivot a
                 else
                   go (l+1) h i pivot a
            else do
              M.swap a (h+1) i
              return i

test = quickCheck $ \(v :: Vector Int) ->
  (quickSort v) == (fromList $ sort (toList v))