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

Question

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.