4 ms·
The problem with radix sort is the same problem in general with big-O notation: A factor of log(n) (or less) difference can often be overwhelmed for all practi
by TheLoneWolfling 12y ago
The problem with radix sort is the same problem in general with big-O notation:
A factor of log(n) (or less) difference can often be overwhelmed for all practical inputs by a constant factor.
- sika_grr 12y agoNo. For radix sort this constant factor is quite low, so it outperforms std::sort in most cases. Try sorting a million integers, my results are: std::sort: 60 ms; radix-sort (LSB, hand coded, less than 20 lines): 11 ms. It gets even better when you mix MSB with LSB for better locality. No, there are no problems with doubles or negative integers. For sizeof(key_value)<=16 B (8 for key, 8 for pointer), radix is the best sort on desktop computers.