Sorting in linear time?
algorithm, complexity-theory, sorting, time-complexity
Solution
Also take a look at related sorts too: pigeonhole sort or counting sort, as well as radix sort as mentioned by Pukku.
Problem
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.