ImperativeQuicksort.hs

module ImperativeQuickSort (quicksort) where

import Prelude hiding (take,drop,length,tail,init)
import Data.Vector (modify,Vector)
import Data.Vector.Generic.Mutable hiding (modify)

-- | Imperative quicksort with O(log n) auxilary space (on top of returned vector) 
quicksort :: Ord a => Vector a -> Vector a
quicksort = modify qsort' 
  where
    qsort' vec
      | length vec < 2 = return ()
      | otherwise      = do
         middle <- partition vec (length vec - 1)
         qsort' $ take middle       vec --left
         qsort' $ drop (middle + 1) vec --right

    partition vec j = do
      pivot <- vec `unsafeRead` j
      i <- unstablePartition (< pivot) (init vec)
      swap vec i j
      return i