How is quicksort is related to cache?

Question

I have seen many places say quicksort is good because it fits to cache-related stuff, such as said in wiki

Additionally, quicksort's sequential and localized memory references work well with a cache

http://en.wikipedia.org/wiki/Quicksort

Could anyone give me some insight about this claim? How is quicksort related to cache? Normally what means that cache in the statement? Why quicksort is better for a cache?

Thanks

Answer 1

quicksort changes the array inplace - in the array it is working on [unlike merge sort, for instance - which creates a different array for it]. Thus, it applies the principle of locality of reference.

Cache benefits from multiple accesses to the same place in the memory, since only the first access needs to be actually taken from the memory - the rest of the accesses are taken from cache, which is much faster the access to memory.

Merge sort for instance - needs much more memory [RAM] accesses - since every accessory array you create - is accessing the RAM again.

Trees are even worse - since 2 sequential accesses in a tree are not likely to be close to each other. [Cache is filled in blocks, so for sequential accesses - only the first byte in the block is a "miss" and the others are a "hit"].