For sorting 10^9 unique 9-digit numbers, would radix sort or counting sort be faster, and why?

For sorting $$10^9$$ unique 9-digit numbers, would radix sort or counting sort be faster, and why?

I know that radix sort is $$O(nk)$$ and counting sort is $$O(n+k)$$, but can’t understand how to apply this.

• Why not program both and see which one is faster in practice? – Yuval Filmus Feb 20 at 18:18
• As far as natural numbers representable with nine decimal digits are concerned, a question about $10^9$ unique ones looks a trick question even allowing leading zeroes. – greybeard Feb 20 at 19:06

We can fill in the numbers for both:

The complexity of radix sort is $$O(nk)$$ with $$k$$ being the size of the numbers. Therefore we get approximately $$9 \cdot 10^9 = 9.000.000.000$$ iterations for Radix sort.

Count Sort

The complexity of radix sort is $$O(n+k)$$ with $$k$$ being the range of the numbers. In the worst case the range is $$10^{9} -1$$. So we get approximately $$10^{9}-1 + 10^9 = 2.000.000.000$$ iterations for count sort.

So count sort would be faster.

• Except it depends on the constant factor hidden by Landau notation... – orlp Feb 20 at 19:33
• Thank you so much. This matched the solution and the reasoning helps me understand how to apply the complexity function. – Zachypoo Feb 20 at 21:52
• You should note that orlp is right and this is not the exact number of operations, but it approximates a factor which is multiplied by the number of operations in each function. I edited my answer to state it more correctly – Nathan Feb 20 at 21:55

There are exactly 10^9 unique nine digit numbers, so the sorted array is just 0, 1, 2, 3, ..., 999,999,999.