5 ms·
It still doesn't improve any on a quick-sort because quicksort is going to run in O(nlog n)=O(n64)=O(N) as well. So what's the point?
by micahbright 9y ago
It still doesn't improve any on a quick-sort because quicksort is going to run in O(nlog n)=O(n64)=O(N) as well. So what's the point?
- contravariant 9y agoIt's hardly fair to assume you can compare two k-bit objects in O(1), logically it should be at least O(k) (got to read every bit at some point). Which would make quicksort O(k n log n) rather than radix sort's O(k n).
- rocqua 9y agoFor the quick-sort case, log n need not be 64. That presumes no duplicates. In the problem to be solved. duplicates matter. Now, in practice it seems unlikely that more than 2^64 integers will need to be sorted, but for the rigor of asymptotic notation, you need to consider that case. I'd like to add that the tree-structure needed for radix sort is going to make it useless in practice. Trees are essentially synonymous with cache-misses.