快速排序 "friendly" 到 on-CPU 缓存？
Is quicksort "friendly" to on-CPU caches?
假设要排序的数组比最大的 on-CPU 缓存大得多（至少大两个数量级）。
由于快速排序涉及将高于枢轴的值移动到枢轴之上，反之亦然
相反，我想它在排序的开始阶段不是很 CPU-缓存友好？
在后期阶段（小子数组）它可能对缓存友好，但在初始阶段的成本如何？
有没有人计算过一些关于缓存未命中和缓存命中成本的公式，以及它如何影响快速排序的总体成本？
high-performance 语言中的典型排序算法不会像理论所建议的那样在一个元素处停止递归，而是在 2^N 个元素（16 个左右）处停止递归，以便在最后阶段使用硬编码排序。这使高速缓存行内的排序保持高效。
不过，在初始阶段，两个元素被 200 或 20000 个元素分隔并不重要。无论哪种方式，它们都在不同的缓存行上。
假设要排序的数组比最大的 on-CPU 缓存大得多（至少大两个数量级）。
由于快速排序涉及将高于枢轴的值移动到枢轴之上，反之亦然 相反，我想它在排序的开始阶段不是很 CPU-缓存友好？
在后期阶段（小子数组）它可能对缓存友好，但在初始阶段的成本如何？
有没有人计算过一些关于缓存未命中和缓存命中成本的公式，以及它如何影响快速排序的总体成本？
high-performance 语言中的典型排序算法不会像理论所建议的那样在一个元素处停止递归，而是在 2^N 个元素（16 个左右）处停止递归，以便在最后阶段使用硬编码排序。这使高速缓存行内的排序保持高效。
不过，在初始阶段，两个元素被 200 或 20000 个元素分隔并不重要。无论哪种方式，它们都在不同的缓存行上。