0

I have n numbers between 0 and (n^4 - 1) what is the fastest way I can sort them.

Of course, nlogn is trivial, but I thought about the option of Radix Sort with base n and than it will be linear time, but I am not sure because of the -1.

Thanks for help!

2 Answers 2

0

I think you are misunderstanding the efficiency of Radix Sort. From Wikipedia:

Radix sort complexity is O(wn) for n keys which are integers of word size w. Sometimes w is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which all perform O(n log n) comparisons to sort n keys. However, in general w cannot be considered a constant: if all n keys are distinct, then w has to be at least log n for a random-access machine to be able to store them in memory, which gives at best a time complexity O(n log n).

I personally would implement quicksort choosing an intelligent pivot. Using this method you can achieve about 1.188 n log n efficiency.

2
  • 1
    If it was n^4 we could represent the numbers in base n and achieve O(4n) hence O(n) time, but the -1 is my problem...
    – nadir
    Aug 31, 2015 at 17:34
  • I see your problem now. I'll ask my algorithms professor after class tomorrow and see what he says.
    – DrewB
    Sep 1, 2015 at 0:55
0

If we use Radix Sort in base n we get the desired linear time complexity, the -1 doesn't matter.

We will represent the numbers in base n:

Then we get : <= (log(base n) of (n^4 - 1)) * (n + n) <= 4 * (2n) <= O(n).

n is for n numbers, the other n is just the digits span (overestimate) and log of n^4 - 1 is less than log n^4 which is 4 in base n. Overall linear time complexity.

Thanks for the help anyway! If I did something wrong please notify me!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.