Safe Haskell	Safe-Inferred
Language	GHC2021

Data.Vector.Sort.Merge

Synopsis

inversionNumber :: (Vector v a, Ord a) => v a -> Int
mergeSort :: (MVector mv a, Ord a, PrimMonad m) => mv (PrimState m) a -> m Int
mergeSortBy :: (MVector mv a, PrimMonad m) => (a -> a -> Ordering) -> mv (PrimState m) a -> m Int
mergeSort_ :: (MVector mv a, Ord a, PrimMonad m) => mv (PrimState m) a -> m ()
mergeSortBy_ :: (MVector mv a, PrimMonad m) => (a -> a -> Ordering) -> mv (PrimState m) a -> m ()
insertionSort :: (MVector mv a, Ord a, PrimMonad m) => mv (PrimState m) a -> m Int
insertionSortBy :: (MVector mv a, PrimMonad m) => (a -> a -> Ordering) -> mv (PrimState m) a -> m Int
insertionSort_ :: (MVector mv a, Ord a, PrimMonad m) => mv (PrimState m) a -> m ()
insertionSortBy_ :: (MVector mv a, PrimMonad m) => (a -> a -> Ordering) -> mv (PrimState m) a -> m ()

Documentation

inversionNumber :: (Vector v a, Ord a) => v a -> Int Source #

>>> import qualified Data.Vector.Unboxed as U
>>> inversionNumber $ U.fromList "312"
2
>>> inversionNumber $ U.fromList "100"
2
>>> inversionNumber $ U.fromList "123"
0

mergeSort Source #

Arguments

:: (MVector mv a, Ord a, PrimMonad m)
=> mv (PrimState m) a
-> m Int	inversion number

>>> import qualified Data.Vector.Unboxed as U
>>> U.modify mergeSort_ $ U.fromList "3610425"
"0123456"
>>> import Data.List (sort)
prop> \(xs::[Int]) -> U.fromList (sort xs) == U.modify mergeSort_ (U.fromList xs)
+++ OK, passed 100 tests.

mergeSortBy Source #

Arguments

:: (MVector mv a, PrimMonad m)
=> (a -> a -> Ordering)
-> mv (PrimState m) a
-> m Int	inversion number

mergeSort_ :: (MVector mv a, Ord a, PrimMonad m) => mv (PrimState m) a -> m () Source #

mergeSortBy_ :: (MVector mv a, PrimMonad m) => (a -> a -> Ordering) -> mv (PrimState m) a -> m () Source #

insertionSort Source #

Arguments

:: (MVector mv a, Ord a, PrimMonad m)
=> mv (PrimState m) a
-> m Int	inversion number

>>> import qualified Data.Vector.Unboxed as U
>>> U.modify insertionSort_ $ U.fromList "3610425"
"0123456"
>>> U.modify insertionSort_ $ U.fromList ""
""
>>> U.modify insertionSort_ $ U.fromList "x"
"x"
>>> U.modify insertionSort_ $ U.fromList "ba"
"ab"
>>> import Data.List (sort)
prop> \(xs::[Int]) -> U.fromList (sort xs) == U.modify insertionSort_ (U.fromList xs)
+++ OK, passed 100 tests.

insertionSortBy Source #

Arguments

:: (MVector mv a, PrimMonad m)
=> (a -> a -> Ordering)
-> mv (PrimState m) a
-> m Int	inversion number

insertionSort_ :: (MVector mv a, Ord a, PrimMonad m) => mv (PrimState m) a -> m () Source #

insertionSortBy_ :: (MVector mv a, PrimMonad m) => (a -> a -> Ordering) -> mv (PrimState m) a -> m () Source #