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

algorithm sorting radix-sort
JAN picture JAN · Aug 20, 2012 · Viewed 8.5k times · Source

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

mbeckish picture mbeckish · Aug 20, 2012

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)).

Related questions

What is the difference between bucket sort and radix sort?

Bucket sort and radix sort are close cousins; bucket sort goes from MSD to LSD, while radix sort can go in both "directions" (LSD or MSD). How do both algorithms work, and in particular how do they differ?

Read More
Radix Sort implemented in C++

I am trying to improve my C++ by creating a program that will take a large amount of numbers between 1 and 10^6. The buckets that will store the numbers in each pass is an array of nodes (where node is a …

Read More
When should we use Radix sort?

It seems Radix sort has a very good average case performance, i.e. O(kN): http://en.wikipedia.org/wiki/Radix_sort Yet it seems like most people are still using Quick Sort - why is this?

Read More