Quicksort using 3-way partitioning

3wayqs.hs

import Data.Vector (Vector (..), (!), (//))
import qualified Data.Vector as V
import Data.List (sort)
import Test.QuickCheck

-- partition the given array using 3-way partitioning
partition :: (Ord a) => Int -> Int -> Vector a -> (Vector a,Int,Int)
partition lo hi a = partition' lo lo hi a
  where partition' i lt gt a
          | i > gt    = (a,lt,gt)
          | otherwise = case compare (a ! i) (a ! lt) of
                             LT -> partition' (i+1) (lt+1) gt $ exchange lt i a
                             GT -> partition' i lt (gt-1) $ exchange gt i a
                             EQ -> partition' (i+1) lt gt a
        exchange ix1 ix2 a =
            let x = a ! ix1
                y = a ! ix2
             in a // [(ix1,y),(ix2,x)]

quicksort :: (Ord a) => Vector a -> Vector a
quicksort a = quicksort' 0 (V.length a-1) a
  where quicksort' lo hi a
         | hi <= lo      = a
         | otherwise     = let (a',lt,gt) = partition lo hi a
                               -- sort elements to the right
                               a''        = quicksort' lo (lt-1) a'
                               -- sort elements to the left
                               a'''       = quicksort' (gt+1) hi a''
                            in a'''

-- Tests

propIdempotent :: [Integer] -> Bool
propIdempotent a = let a' = V.fromList a
                    in (quicksort . quicksort) a' == quicksort a'

propSorted :: [Integer] -> Bool
propSorted a = quicksort (V.fromList a) == V.fromList (sort a)

propMinimum :: [Integer] -> Bool
propMinimum a = let a' = V.fromList a
                 in null a || (V.head . quicksort) a' == minimum a

main = mapM_ quickCheck [propSorted, propIdempotent,propMinimum]