module Data.Array.Vector.Algorithms.Insertion
( sort
, sortBy
, sortByBounds
, sortByBounds'
, Comparison
) where
import Control.Monad.ST
import Data.Array.Vector
import Data.Array.Vector.Algorithms.Common
import qualified Data.Array.Vector.Algorithms.Optimal as O
sort :: (UA e, Ord e) => MUArr e s -> ST s ()
sort = sortBy compare
sortBy :: (UA e) => Comparison e -> MUArr e s -> ST s ()
sortBy cmp a = sortByBounds cmp a 0 (lengthMU a)
sortByBounds :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> ST s ()
sortByBounds cmp a l u
| len < 2 = return ()
| len == 2 = O.sort2ByOffset cmp a l
| len == 3 = O.sort3ByOffset cmp a l
| len == 4 = O.sort4ByOffset cmp a l
| otherwise = O.sort4ByOffset cmp a l >> sortByBounds' cmp a l (l + 4) u
where
len = u l
sortByBounds' :: (UA e) => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()
sortByBounds' cmp a l m u = sort m
where
sort i
| i < u = do v <- readMU a i
insert cmp a l v i
sort (i+1)
| otherwise = return ()
insert :: (UA e) => Comparison e -> MUArr e s -> Int -> e -> Int -> ST s ()
insert cmp a l = loop
where
loop val j
| j <= l = writeMU a l val
| otherwise = do e <- readMU a (j 1)
case cmp val e of
LT -> writeMU a j e >> loop val (j 1)
_ -> writeMU a j val