归并-插入混合排序触发插入排序的最优元素个数阈值X是多少

你给出的混合排序实现逻辑如下：

mergesort(arr, start, end)
  if (end - start <= X)
    perform insertionsort
  else if (end - start > X)
    mergesort(arr, start, mid)
    mergesort(arr, mid+1, end)
    merge(arr, start, end)

这个实现的核心逻辑是利用插入排序在小数据集下极低的常数因子优势，抵消归并排序的递归开销、合并操作开销，最终拿到比纯归并排序更好的性能。最优X的本质是插入排序和归并排序的性能交叉点，也就是子数组长度等于X时，两种排序的耗时基本相等，具体确定方法可以参考下面几个维度：

• 通用场景直接选基准值
  不考虑特殊硬件、业务场景的话，直接选10~30区间的数值即可，推荐优先试15或者20。这个区间是工业界经过大量通用场景验证的最优值范围，很多编程语言标准库的排序实现（比如早期版本的Java Arrays.sort）用的就是这个区间的阈值，不需要额外测试就能拿到比纯归并排序高15%左右的性能。

• 特定环境跑基准测试拿精准值
  如果你需要适配当前运行环境的最优性能，直接做对比测试即可，步骤非常简单：

  1. 生成多组长度覆盖5~50的随机测试数组，每个长度准备至少1000组样本消去随机误差
  2. 固定编译参数、运行环境，分别测试每个长度下插入排序、归并排序的平均耗时
  3. 找到两种排序耗时相等的长度，就是当前环境下的最优X
     注意测试时的编译优化等级、运行硬件要和最终上线的环境完全一致，O0编译和O3编译出来的最优X可能差5~10个数值。

• 结合业务场景调整
  你还可以根据实际排序的元素特性调整X的取值：

  • 如果排序元素的比较操作耗时远高于元素移动/交换的耗时（比如长字符串、自定义复杂对象），X可以适当调小，因为插入排序的比较次数随长度增长更快，大X反而会拉高耗时
  • 如果排序的是整型、浮点型这种比较成本极低的元素，X可以适当调大，最多可以到40左右依然能保持性能优势
  • 如果元素尺寸刚好适配CPU缓存行大小，也可以适当调大X，插入排序的顺序内存访问特性会把缓存优势拉到最大

最后可以用全量排序做验证：拿你选的X跑1e5以上规模的随机数组排序，只要耗时比纯归并排序低10%~30%都是合理区间。

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