uvector-algorithms-0.1: Efficient algorithms for uvector unboxed arrays

PortabilityNon-portable (scoped type variables, bang patterns)
MaintainerDan Doel <dan.doel@gmail.com>



This module provides a radix sort for a subclass of unboxed arrays. The radix class gives information on * the number of passes needed for the data type

  • the size of the auxiliary arrays
  • how to compute the pass-k radix of a value

Radix sort is not a comparison sort, so it is able to achieve O(n) run time, though it also uses O(n) auxiliary space. In addition, there is a constant space overhead of 2*size*sizeOf(Int) for the sort, so it is not advisable to use this sort for large numbers of very small arrays.

A standard example (upon which one could base their own Radix instance) is Word32:

  • We choose to sort on r = 8 bits at a time
  • A Word32 has b = 32 bits total

Thus, b/r = 4 passes are required, 2^r = 256 elements are needed in an auxiliary array, and the radix function is:

 radix k e = (e `shiftR` (k*8)) .&. 256



sort :: forall e s. Radix e => MUArr e s -> ST s ()Source

Sorts an array based on the Radix instance.

class UA e => Radix e whereSource


passes :: e -> IntSource

The number of passes necessary to sort an array of es

size :: e -> IntSource

The size of an auxiliary array

radix :: Int -> e -> IntSource

The radix function parameterized by the current pass