Data.Primitive.Sort

Sort primitive arrays with a stable sorting algorithm. All functions in this module are marked as INLINABLE, so they will specialize when used in a monomorphic setting.

Immutable

sort :: (Contiguous arr, Element arr a, Ord a) => arr a -> arr a

Sort an immutable array. Duplicate elements are preserved.

>>> sort ([5,6,7,9,5,4,5,7] :: Array Int)
fromListN 8 [4,5,5,5,6,7,7,9]

sortUnique :: (ContiguousU arr, Element arr a, Ord a) => arr a -> arr a

Sort an immutable array. Only a single copy of each duplicated element is preserved.

>>> sortUnique ([5,6,7,9,5,4,5,7] :: Array Int)
fromListN 5 [4,5,6,7,9]

sortTagged

Arguments

:: forall k v karr varr. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)

=> karr k

keys

-> varr v

values

-> (karr k, varr v)

Sort a tagged immutable array. Each element from the keys array is paired up with an element from the values array at the matching index. The sort permutes the values array so that a value end up in the same position as its corresponding key. The two argument array should be of the same length, but if one is shorter than the other, the longer one will be truncated so that the lengths match.

>>> sortTagged ([5,6,7,5,5,7] :: Array Int) ([1,2,3,4,5,6] :: Array Int)
(fromListN 6 [5,5,5,6,7,7],fromListN 6 [1,4,5,2,3,6])

Since the sort is stable, the values corresponding to a key that appears multiple times have their original order preserved.

sortUniqueTagged

Arguments

:: forall k v karr varr. (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)

=> karr k

keys

-> varr v

values

-> (karr k, varr v)

Sort a tagged immutable array. Only a single copy of each duplicate key is preserved, along with the last value from values that corresponded to it. The two argument arrays should be of the same length, but if one is shorter than the other, the longer one will be truncated so that the lengths match.

>>> sortUniqueTagged ([5,6,7,5,5,7] :: Array Int) ([1,2,3,4,5,6] :: Array Int)
(fromListN 3 [5,6,7],fromListN 3 [5,2,6])

Mutable

sortMutable :: (Contiguous arr, Element arr a, Ord a) => Mutable arr s a -> ST s (Mutable arr s a)

Sort the mutable array. This operation preserves duplicate elements. The argument may either be modified in-place, or another array may be allocated and returned. The argument may not be reused after being passed to this function.

sortUniqueMutable :: (ContiguousU arr, Element arr a, Ord a) => Mutable arr s a -> ST s (Mutable arr s a)

Sort an immutable array. Only a single copy of each duplicated element is preserved. This operation may run in-place, or it may need to allocate a new array, so the argument may not be reused after this function is applied to it.

sortTaggedMutable :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v) => Mutable karr s k -> Mutable varr s v -> ST s (Mutable karr s k, Mutable varr s v)

Sort an array of a key type k, rearranging the values of type v according to the element they correspond to in the key array. The argument arrays may not be reused after they are passed to the function.

sortUniqueTaggedMutable

Arguments

:: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)

=> Mutable karr s k

keys

-> Mutable varr s v

values

-> ST s (Mutable karr s k, Mutable varr s v)