Random memory accesses are very expensive. This is because TLB misses are typically resolved using a tree data structure (a hash table is not a good choice as k

Random memory accesses are very expensive. This is because TLB misses are typically resolved using a tree data structure (a hash table is not a good choice as knowledge of the hash function would allow for timing attacks). This tree has logarithmic depth (although with a large base). Huge pages make this a lot cheaper, but if they are not used, you might well end up with a situation where n accesses to random positions in a very large array of size n are similarly expensive to sorting the array.