4 ms·
And you're saying that's better than doing both predictable (though perhaps not linear) reads and writes, which most sorting algorithms do? I can believe Radix
by wfunction 11y ago
And you're saying that's better than doing both predictable (though perhaps not linear) reads and writes, which most sorting algorithms do?
I can believe Radix Sort is faster, but I have a harder time believing that it's due to better cache performance.
- TheLoneWolfling 11y agoName 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.