Portability | Non-portable (scoped type variables, bang patterns) |
---|---|

Stability | Experimental |

Maintainer | Dan 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

# Documentation

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

Sorts an array based on the Radix instance.