dev*_*nut 3 language-agnostic algorithm mergesort quicksort
在与quicksortvs 相关的答案中mergesort,通常表示quicksort利用缓存局部性(引用的局部性)比mergesort.
由于这两种方法遵循分而治之的方法,我不明白如何quicksort更加缓存友好.任何人都可以提供更多相关的见解吗？
此外,还有关于就地合并排序的注释.如果这是实用的(我不知道是否),合并排序也可以缓存友好吗？
如果要对适合缓存的数组进行排序,那么quicksort将需要更少的内存访问,因为mergesort需要分配第二个数组.Quicksort会将数组加载到缓存中,然后在不等待内存的情况下继续运行.Mergesort将支付访问第二个阵列的额外费用.
如果你选的是不适合高速缓存的数组,然后快速排序仍从一个地方点获胜,因为他们改乘更小的部分进行排序,这两种算法很快就会到的部分不放入高速缓存,以及通过上述论点,这些快速排序更快.在不适合缓存的排序的较高级别上,quicksort和mergesort从缓存局部性的角度来看几乎等效.