快速排序如何比归并排序更擅长于缓存局部性？

Question

7

在涉及到快速排序与归并排序的答案中, 通常会说快速排序比归并排序更好地利用了缓存局部性（引用局部性）。

由于两种排序都采用了分治方法，我不明白为什么快速排序更加友好。有人能提供更多相关见解吗？

此外，还有关于原地归并排序的注释。如果这是可行的（我不知道是否可行），那么归并排序也可以成为缓存友好型吗？

- dev_nut

这是一个好问题。至少在维基百科页面上我找不到答案。 - displayName

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Timmermans · Accepted Answer

如果您正在对适合缓存的数组进行排序，则快速排序将需要较少的内存访问，因为归并排序需要分配第二个数组。快速排序将数组加载到缓存中，然后继续而无需等待内存。归并排序将支付访问第二个数组的额外费用。

如果您要对不适合缓存的数组进行排序，则从局部性角度来看，快速排序仍然胜出，因为当它们递归地对较小的部分进行排序时，两种算法很快就会到达适合缓存的部分，对于这些部分，快速排序比上述论点更快。在不适合缓存的排序的较高级别上，从缓存局部性的角度来看，快速排序和归并排序表现几乎相同。