79426010

Date: 2025-02-10 03:07:07
Score: 0.5
Natty:
Report link

Based on the formula you wrote, quicksort can be faster than radix sort if you do the math. Let's say you have 10^9 (1 Billion) elements to sort and the biggest element you have is 2^32. Radix sort will need 32 iterations to sort 10^9 items while quick sort will only need log2(10^9) iterations which is 30. This is not even taking into account the inefficiencies of constantly moving elements around which makes in-place sorting far superior. So yeah constraints matter a lot.

Another research showed Quicksort makes 1.37x more comparisons on average since the pivot element is not likely to divide the elements evenly. On average it does an uneven split and ends up making more comparisons. But even with this inefficiency it's faster than algorithms that move elements around again and again.

Reasons:
  • Long answer (-0.5):
  • No code block (0.5):
  • Low reputation (0.5):
Posted by: Chirag Arora