Copyright | (c) 2024 Soumik Sarkar |
---|---|
License | BSD-3-Clause |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
A stable adaptive mergesort implementation.
The merging strategy used is "2-merge" as described by
- Sam Buss, Alexander Knop, "Strategies for Stable Merge Sorting", 2018, https://arxiv.org/abs/1801.04641
Synopsis
- sortArrayBy :: (a -> a -> Ordering) -> MutableArray# s a -> Int -> Int -> ST s ()
- sortIntArrayBy :: (Int -> Int -> Ordering) -> MutableByteArray# s -> Int -> Int -> ST s ()
Documentation
:: (a -> a -> Ordering) | comparison |
-> MutableArray# s a | |
-> Int | offset |
-> Int | length |
-> ST s () |
\(O(n \log n)\). Sort a slice of a MutableArray#
using a comparison
function.
The comparison must form a total order, as required by the Ord
laws.
offset
and length
must be valid, i.e.
0 <= offset < array size
.0 <= length
.offset + length <= array size
.
This function will inline to get the best performance out of statically known comparison functions. To avoid code duplication, create a wrapping definition and reuse it as necessary.
:: (Int -> Int -> Ordering) | comparison |
-> MutableByteArray# s | |
-> Int | offset in |
-> Int | length in |
-> ST s () |
\(O(n \log n)\). Sort a slice of a MutableByteArray#
interpreted as an
array of Int#
s using a comparison function.
The comparison must form a total order, as required by the Ord
laws.
offset
and length
must be valid, i.e.
0 <= offset < array size
.0 <= length
.offset + length <= array size
.
This function will inline to get the best performance out of statically known comparison functions. To avoid code duplication, create a wrapping definition and reuse it as necessary.