4 ms·
Name me another sorting algorithm that does no reads that cannot be predicted several hundred cycles in advance, and O(1) writes to locations that are read from
by TheLoneWolfling 11y ago
Name me another sorting algorithm that does no reads that cannot be predicted several hundred cycles in advance, and O(1) writes to locations that are read from within several hundred cycles. I don't know of any.
Remember: a cache miss costs easily several hundred cycles.
And, to ask a question: if radix sort is faster, and not due to better cache performance, what is it due to?
- wfunction 11y ago> if radix sort is faster, and not due to better cache performance, what is it due to? Uhm, perhaps its time complexity?
- TheLoneWolfling 11y agoUnless you're sorting >2<number of bits / element> elements, that logarithmic factor will be better than the constant of radix sort. Asymptotic complexity with (sub)logarithmic factors is iffy at best, and this is a shining example thereof.