> Radix sort looks fast, with its O(n)O(n) worst-case time complexity. But, if you're using it to sort binary numbers, then there's a hidden constant factor that's usually 32 or 64 (depending on how many bits your numbers are). That's often way bigger than O(\lg(n))O(lg(n)), meaning radix sort tends to be slow in practice.<p>The constant factor in radix sort isn't the number of bits, it's the number of digits. Since one typically sorts on a computer using 8-bit 'digits', that's a constant factor of 4 or 8 (not 32 or 64).
Of course in the real world for problems where sorting is actually the bottleneck and not just something you want not to kill your app's performance, you end up with things like timsort that destroy all these in practice.
I think it's important to mention that counting sort and radix sort are not "true" comparison-based sorts: they have additional requirements on the input data.
Who is still asking candidates to talk about sorting algorithms?<p>It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
Curious: did people notice that you can click on each algorithm and click the blue button to get a detailed write up of how it works? (Or is that too hard to find?)
There is also sorting networks. If you have to sort short list of items, it's probably the best solution around.<p><a href="https://en.wikipedia.org/wiki/Sorting_network" rel="nofollow">https://en.wikipedia.org/wiki/Sorting_network</a>
The best real sorting algorithms are often hybrid.<p>Would be nice to see mention of parallel sorting algorithms. These have basically linear speedup and you can do them on GPUs.<p>Obvious disclaimer that you should never care about your sorting algorithm choice until you need to. Performance is more often IO or memory related than compute. Tech interviews are daft, etc.
Best case for heapsort is actually O(n). Build heap always takes O(n). Then e.g. when all keys are the same, the max-heapify call will take O(1) instead of O(logn).