Sort n numbers between [0,n^2 - 1] in O(n)? [duplicate]

Question

This question already has answers here:

Closed 8 years ago.

Possible Duplicate:
An array of length N can contain values 1,2,3 … N^2. Is it possible to sort in O(n) time?

Given n numbers at the range [0,n^2 -1] how can we sort them in O(n) run time ?

I have a feeling that the solution involves radix sort ,but I'm still missing something.

The n numbers are integers .

Any ideas ?

REMARK: not homework!

Regards

Answer 1

The actual time will depend on the distribution of data that you have, but I would do the following:

• Make n buckets.
• Go through each number and put element with value i into bucket sqrt(i).
• Go through each bucket, and perform radix sort on each element in the bucket.

Answer 2

I think you're out of luck. Radix sort is O(k*n), where k is number of digits. In your case, k = log(n^2), resulting in O(n*log(n)).