7

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?

dev_nut
  • 2,476
  • 4
  • 29
  • 49

1 Answers1

8

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.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • 1
    Even though, the in-place is more complicated, isn't [merge sort also possible without a scratch array](http://penguin.ewu.edu/cscd300/Topic/AdvSorting/MergeSorts/InPlace.html)? Does your answer consider the in-place version? – dev_nut Jan 30 '18 at 04:23
  • There isn't really a practical in-place merge sort that has the same O( N log N ) complexity as regular merge sort. – Matt Timmermans Jan 30 '18 at 04:26
  • Could you kindly, expand upon this in your answer? Then, I think all of the doubts would be clarified. – dev_nut Jan 30 '18 at 04:43
  • 2
    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. – Matt Timmermans Jan 30 '18 at 05:08
  • @MattTimmermans: there are in-place merge sorts that still are O(N log N). See http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.8523&rep=rep1&type=pdf. 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. – Jerry Coffin Feb 05 '18 at 04:42
  • 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. – garbagecollector Nov 07 '21 at 18:49