归并排序实现中复制合并数组到原数组为何需两个循环变量

你写的单循环回写代码跑错，本质是没对齐两个数组的有效索引范围，和代码里显式用几个循环变量没有直接关系，具体逻辑拆解开很简单：

• 归并排序的sort方法从来不是处理完整的原数组，每次调用只操作原数组上[si, ei]这个闭区间的子段：递归拆分过程中，可能处理左半段、右半段，甚至是长度只有2、3的极小分段，根本不会覆盖从0到数组末尾的全部位置。
• 临时数组merged的长度是ei - si + 1，它只存当前处理分段归并完成的排序结果，和原数组的总长度没有一一对应关系。

拿你给的测试数组{1,8,0,7,-4}举个实际运行的例子：第一次拆分时mid值为2，右半段的处理范围是si=3, ei=4，对应原数组里的元素是7、-4，这时候merged长度只有2，存的是排好序的[-4,7]。如果用你写的单循环从i=0开始给arr[i]赋值，会直接把原数组索引0、1位置的1、8覆盖成-4、7，直接弄坏其他分段还没参与归并的元素，最后结果肯定不对。

你参考代码里的双变量写法逻辑非常直白：

• 变量i从0开始遍历merged，按顺序把临时数组里排好的结果读出来
• 变量j从当前分段的起始位置si开始遍历原数组，把读到的值写到正确的待覆盖位置，完全不会碰本次归并范围外的元素

补充说明：你完全可以不用显式写两个循环变量，只要算对偏移量就行，下面的单变量写法和双变量写法效果完全一样，本质还是做了索引位置的对齐：

for (int i = 0; i < merged.length; i++) {
    arr[si + i] = merged[i];
}

你之前写的单循环会错，核心就是没加这个起始位置的偏移，硬把临时数组的0索引和原数组的0索引绑死了。

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