Data.SamSort

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

Documentation

sortArrayBy

Arguments

:: (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.

sortIntArrayBy

Arguments

:: (Int -> Int -> Ordering)

comparison

-> MutableByteArray# s

-> Int

offset in Int#s

-> Int

length in Int#s

-> 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.