归并排序与归并插入混合排序的比较次数差异规律原因咨询

差值波动的核心成因 #

你观测到的波动本质是归并排序的二分拆分特性与阈值S的离散匹配效应，具体逻辑如下：

• 纯归并排序会递归拆分数组直到子数组长度为1，混合排序则在子数组长度≤S（测试用值为7）时终止递归、转用插入排序。两者的比较次数差值，本质是所有最底层子数组「插入排序的比较次数」减去「纯归并排序处理同等长度子数组的比较次数」的总和。
• 归并排序的二分拆分规则决定了：当n恰好等于2^k * S时，所有最底层子数组的长度刚好为S，总差值达到当前层级的峰值；当n略大于该值时，会出现一批长度小于S的子数组，这批子数组的差值更小甚至为负，总差值随之下降，直到n增长到下一个2^(k+1)*S的节点，总差值再次跳升，刚好对应你观测到的「每轮波动幅度约为前一轮2倍」的规律。
• 你之前参考的时间复杂度是渐进平均复杂度，仅描述n趋近于无穷大时的整体趋势，不覆盖中小规模n下的离散波动特征。你测试的n范围还处于底层子数组拆分结构剧烈变化的区间，因此离散匹配效应占主导，平滑的渐进趋势还未显现。
• 可以通过两个测试验证该逻辑：将S调整为1，此时混合排序和纯归并排序逻辑完全一致，差值恒为0，波动完全消失；将S调整为其他固定值，波动步长会同步变为2的幂次乘以新的S值，和你的猜测完全吻合。

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