为何优化快速排序时小子数组插入排序的截断值具有系统依赖性？

你提到的这个M，是归并排序中当子数组长度小于该值时，切换为插入排序的阈值——这是为了利用插入排序在小数据量下的低常数开销，抵消归并排序的递归/分治开销。

Sedgewick等人所著《Algorithm》第4版第296页提到：最优截断值M具有系统依赖性，但5至15之间的数值在多数场景下表现良好。

为什么它会有系统依赖性？核心原因是抽象的"操作数计数"和实际硬件执行的真实开销并不完全等价：

• 缓存局部性的硬件差异：插入排序的内存访问是连续的，更容易命中CPU缓存；而归并排序需要频繁读写辅助数组，缓存命中率更低。不同系统的CPU缓存大小、缓存行长度、内存延迟差异极大——比如服务器CPU的L3缓存可能有几十MB，嵌入式CPU可能只有几KB，这直接改变了两种排序的相对耗时，最优M自然不同。
• 指令执行的常数因子差异：算法分析里的"一次比较""一次赋值"是抽象的，但实际中，不同处理器对这些操作的执行效率天差地别。比如支持SIMD指令的CPU可以一次比较多个元素，分支预测效率高的CPU能更好处理插入排序里的条件分支，这些硬件特性会改变插入排序和归并排序的性能比值，导致最优M变化。
• 语言与编译的底层优化差异：同样的算法实现，在C语言静态编译、Java JIT即时编译、Python解释执行的环境下，实际生成的指令完全不同。甚至同一语言在不同系统上的编译优化策略（比如GCC在x86和ARM上的优化选项）也会影响性能，进一步让最优M产生系统依赖性。

不过5-15这个区间在多数通用系统上都能取得不错的平衡——因为这个范围刚好覆盖了多数CPU缓存行的大小，同时让插入排序的小数据量优势充分发挥，又不会让归并排序的分治优势损失太多。

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