Performance Quiz #14: Memory Locality, X64 vs. X86, Alignment, and Density

explanation by 'Ryan' on the linked page:

Wait - are you concluding that completely randomized access is the same speed as sequential for very large cases? That would be very surprising!!

What's the range of rand()? If it's 32k that would mean you're just shuffling the first 32k items and doing basically sequential reads for most items in the large case, and the per-item avg would become very close to the sequential case. This matches your data very well.