Question

Show how to sort n integers in the range 0 to (n^3)-1 in O(n) time.
hint: use radix sort

Answer 1

The integers are representable as 3 digits in base n, since they're in range 0-(N^3)-1
so, we can use N buckets, where the buckets are any structure that preserves the insertion order.
1)Empty the buckets
2)Pass through the input, adding the integers to the bucket corresponding to the MSB
3)Append the contents of all buckets to a single structure X in order
4)Empty the buckets
5)Pass through X adding the integers to the bucket corresponding to the middle digit
6)repeat steps 3-5 for the LSB
X now contains the sorted integers
Assuming that insert is a constant time operation for the structure you choose for the buckets this sort must be O(n), as it consists of a constant number of O(n) or better steps.
We know the steps are O(n) or better because they are O(1) or iterators with O(1) bodies, which are O(n)