Sorting faster than n log n?

[getpagesize]

Input is n integers, but we know that they cannot exceed 10 digits, i.e. the largest number is 10^10

How can we take advantage of this to beat O(n log n)? Obviously sheer bucket sort is out of the question with such large numbers, what else can I do to avoid doing a comparison sort such that I can beat O(n log n)?

[mellice]

If the distribution of the numbers is uniform, then I recommend Counting Sort (linear time sort), you can google it

[Zachm]

Radix Sort (http://en.wikipedia.org/wiki/Radix_sort) can give you run-time complexity of O(n).

Regards,
Zachm

[getpagesize]

Radix Sort (http://en.wikipedia.org/wiki/Radix_sort) can give you run-time complexity of O(n).

Regards,
Zachm

How do you obtain O(n) in radix sort?
Bucket sort is O(n), and bucket sort has to be executed at least k times, where k is the maximum number of digits in the array to be sorted, thus radix sort is O(kn), where n is the number of elements in the array to be sorted?

[getpagesize]

Radix Sort (http://en.wikipedia.org/wiki/Radix_sort) can give you run-time complexity of O(n).

Regards,
Zachm

Oh, forgive my earlier post, I did after all say that my numbers were limited by 10 digits hence 10n is O(n) obviously.

But if the maximum number of digits is indeed k, then it is O(kn), right?

[Zachm]

Oh, forgive my earlier post, I did after all say that my numbers were limited by 10 digits hence 10n is O(n) obviously.

But if the maximum number of digits is indeed k, then it is O(kn), right?

Right.

Regards,
Zachm

[staccato]

Hello guys, it is very interesting to know that.
One question. Is quick sort better than both radix sort and bucket sort in practical??

[Uglybb]

Radix and count sorting unfortunately have hideous memory overheads for such size because they have to build histogram tables often called key or index tables.

Radix sort will give OkN on average
Count sorting will give O(N+k) on average

Quicksort with random pivot selection is usually the safest bet for time, speed and overhead