|Portability||Non-portable (scoped type variables, bang patterns)|
|Maintainer||Dan Doel <firstname.lastname@example.org>|
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
Sorts an array based on the Radix instance.
The number of passes necessary to sort an array of es
The size of an auxiliary array
The radix function parameterized by the current pass