Show how to sort \(n\) integers in the range 0 to \(n^3 - 1\) in \(O(n)\) time.
The key is to represent each integer in base \(n\) and use radix sort.
Think of each number as having multiple “digits” when written in base \(n\). Since the maximum value is \(n^3 - 1\), the largest number in base \(n\) has 3 digits (ranging from 0 to \(n - 1\) in each position).
For example, if \(n = 10\), numbers range from 0 to 999, which are naturally 3-digit numbers in base 10.
Convert each integer to base \(n\) representation (we can extract digits using modulo and division), then use radix sort with \(d = 3\) digits, using counting sort with \(k = n - 1\) on each digit.
Each integer in range \([0, n^3 - 1]\) can be represented as:
\[x = x_2 \cdot n^2 + x_1 \cdot n + x_0\]where \(0 \leq x_i < n\) for each digit \(x_i\).
Using radix sort with \(d = 3\) digits, each in range \([0, n - 1]\):
- We make \(d = 3\) passes
- Each pass uses counting sort with \(k = n\), taking \(\Theta(n + k) = \Theta(n + n) = \Theta(n)\) time
- Total time: \(\Theta(d \cdot n) = \Theta(3n) = \Theta(n)\)
For example, with \(n = 10\) and numbers in \([0, 999]\):
- Number 847 becomes \((8, 4, 7)\) in base 10
- Number 23 becomes \((0, 2, 3)\) in base 10
- Sort first on the ones digit, then tens, then hundreds
The algorithm runs in \(\Theta(n)\) time, achieving linear-time sorting!