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.

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?

> if radix sort is faster, and not due to better cache performance, what is it due to?

Uhm, perhaps its time complexity?

Unless 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.