假设要排序的数组比CPU缓存上最大的数组大得多（至少大两个数量级）。
因为快速排序涉及将值移动到高于轴和副轴的轴上
反之，我认为在排序的开始阶段它对cpu缓存不是很友好？
在后期阶段（小的子阵列），它可能是缓存友好的，但在初始阶段的成本如何？
有没有人计算过有关缓存未命中和缓存命中的成本以及它如何影响快速排序的总体成本的公式？
最佳答案
高性能语言中的典型排序算法将停止递归，不再像理论所建议的那样在一个元素处递归，而是在最后阶段使用2^n个元素（16个左右）的硬编码排序。这将使缓存线内的排序保持高效。
不过，在最初的阶段，两个元素是由200个元素还是20000个元素分开并不重要它们都在不同的缓存线上。
关于algorithm - quicksort对CPU上的缓存“友好”吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34851354/