Sort n numbers between [0,n^2 - 1] in O(n)?
algorithm, radix-sort, sorting
Solution
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.
Problem
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