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?

Natiha

This is a good question. I could not find the answer on Wikipedia page at least. – Quadrivalent

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.

Maybellmaybelle

Even though, the in-place is more complicated, isn't merge sort also possible without a scratch array? Does your answer consider the in-place version? – Natiha

There isn't really a practical in-place merge sort that has the same O( N log N ) complexity as regular merge sort. – Maybellmaybelle

Could you kindly, expand upon this in your answer? Then, I think all of the doubts would be clarified. – Natiha

Not sure what you mean... there just isn't one. The link you posted indicates the their in-place merge sort takes O(N^2) time. There are better, easy variants that take O( N log^2 N ), but that is still slower than regular merge sort. There are complicated merge-sort-like algorithms that manage to get O( N log N ) time with minimal extra space, but they are complicated enough that they aren't used in real life. – Maybellmaybelle

@MattTimmermans: there are in-place merge sorts that still are O(N log N). See citeseerx.ist.psu.edu/viewdoc/…. In practice, they are slower than out of place merge sorts though. OTOH, at 1.5x the time for a merge sort, it's around 3x the time for a Quicksort, which is definitely slower than a typical merge sort, but not but a truly terrible amount. – Fumble

In order to perform an in-place merging, you need to find insertion points at which to insert the subarrays on the right side into. That by itself is already an O(lg N) operation. Added the memory shifting which costs another O(N). So merging becomes O(N lg N), which basically reduces to just another sort. There are sublinear merging, but it doesn't actually "merge" the subarrays. – Foodstuff