-2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Why not program both and see which one is faster in practice? $\endgroup$ – Yuval Filmus Feb 20 at 18:18
  • 1
    $\begingroup$ 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. $\endgroup$ – greybeard Feb 20 at 19:06
-2
$\begingroup$

We can fill in the numbers for both:

Radix Sort

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.

$\endgroup$
  • 2
    $\begingroup$ Except it depends on the constant factor hidden by Landau notation... $\endgroup$ – orlp Feb 20 at 19:33
  • 1
    $\begingroup$ Thank you so much. This matched the solution and the reasoning helps me understand how to apply the complexity function. $\endgroup$ – Zachypoo Feb 20 at 21:52
  • $\begingroup$ 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 $\endgroup$ – Nathan Feb 20 at 21:55
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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