In answers related to quicksort
vs mergesort
,通常说 quicksort
比 mergesort
更好地利用缓存局部性(引用局部性)。
由于这两种排序都遵循分而治之的方法,我不明白 quicksort
为什么对缓存更友好。谁能提供更多与此相关的见解?
此外,还有关于 in-place merge sort 的注释.如果这可行(我不知道是否可行),合并排序是否也对缓存友好?
最佳答案
如果您正在对适合缓存的数组进行排序,那么快速排序将需要更少的内存访问,因为合并排序需要分配第二个数组。 Quicksort 会将数组加载到缓存中,然后在不等待内存的情况下继续进行。 Mergesort 将支付访问第二个数组的额外费用。
如果您正在对不适合缓存的数组进行排序,那么从局部性的角度来看,快速排序仍然会胜出,因为当它们递归以对较小的部分进行排序时,这两种算法很快就会到达适合的部分 适合缓存,对于那些快速排序,上述参数更快。在不适合缓存的上层排序中,从缓存局部性的角度来看,快速排序和合并排序的性能几乎相同。
关于algorithm - 与归并排序相比,快速排序在缓存局部性方面有何优势?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48513480/