Sorting in linear time

Question

I am reading introduction to algorithms 2nd edition, and there is a question says that we can sort n integers, who are between 0 and n³-1 in linear time. I am thinking of IBM's radix sort approach. I start with the least significant digit, separate numbers with respect to least significant digit, and then sort, then separate with respect to next least significant digit and so on. Each separation takes O(n) time. But i have a doubt, for example, if one of the number consists of n digits, then the algorithm takes O(1*n+2*n+...+n*n)=O(n²) time, right? Can we assure that numbers consist of fewer than n digits, or can anybody give another hint for the question? Thanks

Answer 1

Radix Sort complexity is O(dn) with d as the number of digits in a number.

The algorithm runs in linear time only when d is constant! In your case d = 3log(n) and your algorithm will run in O(nlog(n)).

I'm honestly not sure how to solve this problem in linear time. Is there any other piece of information regarding the nature of the numbers I'm wondering if there is any other piece of information missing about the nature of numbers...

Answer 2

Assuming a word RAM model, and that n fits in O(1) words, there is a linear time algorithm.

Write every number in base n, and do a radix sort (with a stable version of counting sort as the underlying digit sort).

If you want to assume unbounded n, then the size of the input it actually n log n, in which case radix sort again works (in O(n log n) time), and technically speaking, it is still a linear time algorithm! (Of course, I suppose this still assumes arithmetic is O(1)...)