Data.Vector.Algorithms.Radix

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)) .&. 255