How is quick sort better at cache locality than mergesort?

Question

In answers related to quicksort vs mergesort, it is commonly stated that quicksort exploits cache locality (locality of reference) better than mergesort.

As both sorts follow a divide and conquer approach, I don't understand how quicksort is more cache-friendly. Can anyone provide more insight related to this?

Also, there's notes on in-place merge sort. If this is practical (I have no idea whether it is), can merge sort also be cache-friendly?

Answer 1

If you're sorting an array that fits into cache, then quicksort will require fewer memory accesses just because mergesort needs to allocate a second array. Quicksort will load the array into cache and then proceed without waiting for memory at all. Mergesort will pay the additional cost of accessing the second array.

If you're sorting an array that doesn't fit into cache, then quicksort still wins from a locality point of view, because as they recurse to sort smaller sections, both algorithms will soon get to sections that do fit into cache, and for those quicksort is faster by the above argument. On the upper levels of the sort that don't fit into cache, quicksort and mergesort perform pretty much equivalently from a cache locality point of view.