Program gives the declaration of the `RadixSorter` class.
Notice that the `RadixSorter` class is not a template.
This radix sorter is designed to sort specifically
an array of `unsigned int`s.

Three constants are declared as static members of the
in the `RadixSorter` class--`R`, `r` and `p`.
The constant *R* represents the radix and .
The constant *p* is the number sorting passes needed to sort the data.

The `RadixSorter` class contains one member variable--`count`.
The `count` variable is an array of unsigned integers
used to implement the sorting passes.
The `RadixSorter` constructor simply
initializes the `count` array with length *R*.

**Program:** `RadixSorter` Class Definition

Program defines the constants `R`, `r` and `p`,
and gives the code for the `DoSort` member function
of the `RadixSorter` class.
In this case *r*=8 and .
Therefore, a radix-256 sort is being done.
We have chosen *R* as a power of two because
that way the computations required to implement the radix sort
can be implemented efficiently using simple bit shift and mask operations.
In order to sort *b*-bit unsigned integers,
it is necessary to make
sorting passes.
The constants `r`, `R` and `p` are initialized accordingly.

**Program:** `RadixSorter` Class `DoSort` Member Function Definition

`DoSort` begins by creating a temporary array
of `unsigned int`s of length *n*.
Each iteration of the main loop corresponds to one pass
of the radix sort (lines 9-30).
In all *p* iterations are required.

During the pass of the main loop
the following steps are done:
First, the *R* counters are all set to zero (lines 11-12).
This takes *O*(*R*) time.
Then a pass is made through the input array during which
the number of occurrences of each radix-*R* digit in the
digit position are counted (lines 13-17).
This pass takes *O*(*n*) time.
Notice that during this pass all the input data is copied
into the temporary array.

Next,
the array of counts is transformed into an array of offsets
according to Equation .
This requires a single pass through the counter array (lines 18-24).
Therefore, it takes *O*(*R*) time.
Finally, the data sequence is permuted by copying the values
from the temporary array back into the input array (lines 25-30).
Since this requires a single pass through the data arrays,
the running time is *O*(*n*).

After the *p* sorting passes have been done,
the array of data is sorted.
The running time for the `DoSort` routine
of the `RadixSorter` class is .
If we assume that the size of an integer is 32 bits and given that *R*=256,
the number of sorting passes required is *p*=4.
Therefore, the running time for the radix sort is simply *O*(*n*).
I.e., radix sort is a linear-time sorting algorithm.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.