Copyright | (c) 2008-2010 Dan Doel |
---|---|

Maintainer | Dan Doel |

Stability | Experimental |

Portability | Portable |

Safe Haskell | Safe-Inferred |

Language | Haskell2010 |

Optimal sorts for very small array sizes, or for small numbers of particular indices in a larger array (to be used, for instance, for sorting a median of 3 values into the lowest position in an array for a median-of-3 quicksort).

## Synopsis

- sort2ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()
- sort2ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()
- sort3ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()
- sort3ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()
- sort4ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> Int -> m ()
- sort4ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()
- type Comparison e = e -> e -> Ordering

# Documentation

sort2ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m () Source #

Sorts the elements at the two given indices using the comparison. This
is essentially a compare-and-swap, although the first index is assumed to
be the `lower`

of the two.

sort2ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m () Source #

Sorts the elements at the positions `off`

and 'off + 1' in the given
array using the comparison.

sort3ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m () Source #

Sorts the elements at the three given indices. The indices are assumed to be given from lowest to highest, so if 'l < m < u' then 'sort3ByIndex cmp a m l u' essentially sorts the median of three into the lowest position in the array.

sort3ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m () Source #

Sorts the three elements starting at the given offset in the array.

sort4ByIndex :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> Int -> m () Source #

Sorts the elements at the four given indices. Like the 2 and 3 element versions, this assumes that the indices are given in increasing order, so it can be used to sort medians into particular positions and so on.

sort4ByOffset :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m () Source #

Sorts the four elements beginning at the offset.

type Comparison e = e -> e -> Ordering Source #

A type of comparisons between two values of a given type.