归并排序（Merge Sort）交换次数计数器结果异常问题排查

1. 「交换次数」的定义差异是核心问题 #

你手动计算的4次交换，大概率是基于冒泡排序那种两两相邻元素直接交换的逻辑，但归并排序的核心是通过临时数组完成元素的复制合并，不存在传统意义上的两两交换操作——这是计数器结果和你手动计算值不匹配的根本原因。

拿测试数组{3,8,5,1}举例：
你手动统计的4次交换其实是冒泡排序的操作路径：

1. 8和5交换 → {3,5,8,1}
2. 8和1交换 → {3,5,1,8}
3. 5和1交换 → {3,1,5,8}
4. 3和1交换 → {1,3,5,8}

但归并排序的执行逻辑完全不同：它先拆分到单个元素，再通过临时数组按顺序合并，整个过程没有“两个元素互换位置”的操作，只有元素从原数组到临时数组的复制移动。如果你的计数器把这种复制移动算作“交换”，统计结果自然和手动按冒泡逻辑算的不一样。

2. 比较次数的验证方法 #

要验证比较次数是否正确，你可以手动模拟归并排序的每一次比较：
以{3,8,5,1}为例：

1. 合并[3]和[8]：比较1次（3 vs 8）
2. 合并[5]和[1]：比较1次（5 vs 1）
3. 合并[3,8]和[1,5]：
   • 3 vs 1 → 比较1次
   • 3 vs 5 → 比较1次
   • 8 vs 5 → 比较1次
   • 剩余的8直接复制，无需比较
     总共比较次数为1+1+3=5次。把这个结果和你的计数器输出对比，就能判断是否正确。

3. 计数器逻辑的常见错误点 #

• 交换计数器的逻辑错位：如果代码里把合并时的元素复制操作当作“交换”统计，或者只在特定场景下计数，会和手动的交换定义完全偏离；归并排序本身不存在严格意义上的交换，建议把统计目标改成「元素移动次数」更合理。
• 比较计数器的遗漏或多算：比如合并时，当某一个子数组遍历完成后，剩余元素直接复制，此时不需要比较，如果代码误把这种场景计入比较次数，结果就会偏大；另外要确保每一次left[i]和right[j]的对比都被计数，不要遗漏。
• 递归阶段误统计：归并排序的拆分递归过程不需要比较或交换，如果计数器在递归调用时错误累加，也会导致结果异常。

内容的提问来源于stack exchange，提问作者Anônimo