Sorting (really scanning through an array) is very efficient in cache lines, while hash tables are very inefficient.
In the example, every memory access in hashing gets 8 byte of useful data, while every memory access in sorting gets 64 bytes of useful data.
So you have to be 8x more efficient to win out.
For this problem, the radix sort is log_1024(n) passes, which for a key size of 64 bits can’t ever get above 7 passes.
If you increase the key size then the efficiency win of sorting drops (128 bit keys means you have to run less than 4 passes to win).
Essentially the size of the key compared to the cache line size is a (hidden) part of the big O.
Sorting (really scanning through an array) is very efficient in cache lines, while hash tables are very inefficient.
In the example, every memory access in hashing gets 8 byte of useful data, while every memory access in sorting gets 64 bytes of useful data.
So you have to be 8x more efficient to win out.
For this problem, the radix sort is log_1024(n) passes, which for a key size of 64 bits can’t ever get above 7 passes.
If you increase the key size then the efficiency win of sorting drops (128 bit keys means you have to run less than 4 passes to win).
Essentially the size of the key compared to the cache line size is a (hidden) part of the big O.