为何输入规模增大时Mergesort性能优于Quicksort？

一、性能反转的核心：CPU缓存局部性 #

当数据规模突破CPU L2/L3缓存容量（通常在几十万到几百万元素级别，取决于硬件）时，内存访问延迟会成为性能的决定性因素：

• 快速排序的分区（partition）过程需要左右指针在数组中来回扫描、交换元素，这种随机化的内存访问模式会频繁触发缓存未命中（cache miss）。当数组无法被缓存完全容纳时，每次未命中都需要等待数十倍于CPU周期的内存读取时间，随着数据规模扩大，这种延迟会被急剧放大。
• 归并排序的合并（merge）过程是顺序遍历两个有序子数组，完全契合CPU的预取机制，缓存命中率极高。即便需要额外的O(n)临时空间，这种连续内存访问的效率优势在大数据量下会彻底抵消快排“原地排序”的内存优势。

二、为何末尾元素作为pivot效果最佳？ #

你观察到的现象同样和缓存局部性直接相关：

• 随机pivot或三数取中策略：虽然能从理论上避免O(n²)的最坏时间复杂度，但选择pivot时需要额外访问数组中多个分散位置的元素，这会增加缓存未命中的概率。在大数据量下，这部分额外的内存访问开销会超过避免最坏情况带来的性能收益。
• 选择末尾元素作为pivot：无需额外的跨位置内存访问，直接取用当前子数组的末尾元素，减少了缓存的额外开销。如果你的测试用例是随机生成的数组，这种选择并不会频繁触发最坏情况，反而因为减少了pivot选择阶段的内存操作，整体性能更优。

三、实现层面的优化建议 #

快速排序优化 #

1. 小数据量切换插入排序：当子数组长度小于10~20时，插入排序的常数项开销更低，且缓存局部性更好，能有效减少递归调用和缓存未命中。
2. 尾递归优化：快排的递归深度过大会带来栈开销，可将递归改为迭代，或优先对较大的子数组进行递归，较小的子数组延后处理，减少栈的占用和递归调用开销。
3. 优化分区逻辑：比如采用Hoare分区法（左右指针双向扫描交换）替代Lomuto分区法（单指针遍历交换），能减少交换次数，降低内存访问频率。

归并排序优化 #

1. 预分配临时数组：不要在每次合并时动态分配临时空间，提前一次性分配O(n)的临时数组，避免频繁malloc/free带来的开销，这在大数据量下影响显著。
2. 原地归并（可选）：如果对内存占用有严格要求，可实现原地归并逻辑（如通过数组反转、旋转等技巧），但会增加一定的时间复杂度，需权衡取舍。

四、总结 #

• 50万元素是典型的缓存容量临界点：当数据超出CPU缓存的容纳范围时，内存访问模式的影响远大于算法理论时间复杂度的常数项差异，归并排序的顺序访问优势彻底凸显。
• 末尾pivot的优势在于减少pivot选择阶段的缓存开销，在随机数组场景下不会触发最坏情况，因此表现最优。
• 优化的核心方向是围绕缓存局部性和常数项开销展开，而非单纯依赖理论时间复杂度。

内容的提问来源于stack exchange，提问作者estevao