插入排序与归并排序性能相近的条件及数学推导问询

咱们先从两种排序算法的核心时间复杂度模型入手，这是推导的基础：

• 插入排序：它的运行效率直接和数组里的逆序对数量挂钩，时间复杂度可以写成 $T_{insert}(n, i) = O(n + i)$ —— 这里 $n$ 是数组长度，$i$ 是数组里的逆序对总数。如果数组完全有序（最好情况），逆序对 $i=0$，此时插入排序快得飞起，时间复杂度是 $O(n)$；但要是数组完全逆序（最坏情况），逆序对数量会达到 $\frac{n(n-1)}{2}$，时间复杂度就退化成 $O(n^2)$ 了。
• 归并排序：不管数组乱成什么样，它的时间复杂度都是 $O(n \log n)$，这是分治策略决定的，虽然不同实现的常数因子有差异，但量级是稳定的。

第一步：建立性能相等的等式 #

要找到两者性能打平的临界点，我们可以先假设它们的运行时间相等（这里可以先忽略常数因子，或者用 $C$ 代表归并排序实现的常数项）：
$$
n + i = C \cdot n \log n
$$
接下来我们把逆序对数量 $i$ 解出来：
$$
i = C \cdot n \log n - n
$$

第二步：把逆序对数量和有序占比关联起来 #

咱们定义数组的有序占比：就是有序元素对的数量占总元素对数量的比例。总元素对数量是 $\frac{n(n-1)}{2}$，有序元素对数量等于总元素对减去逆序对数量，也就是 $\frac{n(n-1)}{2} - i$。所以有序占比 $r$ 的公式是：
$$
r = \frac{\frac{n(n-1)}{2} - i}{\frac{n(n-1)}{2}} = 1 - \frac{2i}{n(n-1)}
$$

把刚才解出来的 $i$ 代入这个式子：
$$
r = 1 - \frac{2(C \cdot n \log n - n)}{n(n-1)} = 1 - \frac{2(C \log n - 1)}{n-1}
$$

第三步：分析有序占比和n的关系 #

从这个最终式子就能解释你观察到的现象：

• 当数组越有序（$r$ 越接近1），$\frac{2(C \log n - 1)}{n-1}$ 就得越接近0。而 $\log n$ 的增长速度远慢于 $n$，所以只有当 $n$ 足够大时，这个分式才会趋近于0——这就意味着，数组越有序，需要更大的 $n$ 才能让插入排序和归并排序性能相当。
• 反过来，如果 $n$ 是固定的，数组越无序（$r$ 越小），逆序对 $i$ 就越多，插入排序的时间复杂度会快速向 $O(n^2)$ 靠拢，很快就会被归并排序超过。

聊聊实际代码中的常数因子 #

在实际写代码时，归并排序的常数因子 $C$ 通常比插入排序大，因为归并排序涉及更多递归调用和数组拷贝操作。所以实际的临界点会和理论推导有点偏差——比如当数组非常有序时，插入排序可能在比理论值更大的 $n$ 下才会被归并排序追上，这完全符合你用绘图计算器看到的结果。

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