Given an input set of n integers in the range [0..n^3-1], provide a linear time sorting algorithm.
This is a review for my test on thursday, and I have no idea how to approach this problem.
Have a look at radix sort.