algorithm - 与归并排序相比，快速排序在缓存局部性方面有何优势？

Question

In answers related to quicksort vs mergesort ，通常说 quicksort 比 mergesort 更好地利用缓存局部性(引用局部性)。

由于这两种排序都遵循分而治之的方法，我不明白 quicksort 为什么对缓存更友好。谁能提供更多与此相关的见解？

此外，还有关于 in-place merge sort 的注释.如果这可行(我不知道是否可行)，合并排序是否也对缓存友好？

Answer 1

如果您正在对适合缓存的数组进行排序，那么快速排序将需要更少的内存访问，因为合并排序需要分配第二个数组。 Quicksort 会将数组加载到缓存中，然后在不等待内存的情况下继续进行。 Mergesort 将支付访问第二个数组的额外费用。

如果您正在对不适合缓存的数组进行排序，那么从局部性的角度来看，快速排序仍然会胜出，因为当它们递归以对较小的部分进行排序时，这两种算法很快就会到达适合的部分 适合缓存，对于那些快速排序，上述参数更快。在不适合缓存的上层排序中，从缓存局部性的角度来看，快速排序和合并排序的性能几乎相同。