| Portability | Non-portable (scoped type variables, bang patterns) |
|---|---|
| Stability | Experimental |
| Maintainer | Dan Doel <dan.doel@gmail.com> |
Data.Array.Vector.Algorithms.Radix
Description
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.