归并排序merge函数中最后两个while循环的作用及测试打印方法咨询

一、为什么需要merge函数里的最后两个while循环？ #

咱们先回忆下merge函数的核心职责：它要把两个已经有序的子数组（array[low...mid]和array[mid+1...high]）合并成一个整体有序的数组，临时存到temp里。

第一个while循环（while(i<=mid && j<=high)）是同时遍历两个子数组，每次挑出当前两个子数组中更小的元素放到temp里，再移动对应的指针。但这个循环有个前提：只有当两个子数组都还有未遍历的元素时才会执行——一旦其中一个子数组的元素被全部处理完（比如i超过mid，说明第一个子数组空了；或者j超过high，说明第二个子数组空了），这个循环就会停止。

这时候，另一个子数组里还剩一批元素，这些元素本身是有序的，而且因为两个子数组原本就有序，剩下的元素肯定比已经放到temp里的所有元素都大（毕竟之前的循环已经把两个子数组里更小的元素都取走了）。所以我们需要把这些剩余元素直接追加到temp的末尾，这就是那两个while循环的作用：

• 第一个额外循环（while(i<=mid)）：专门处理第一个子数组还有剩余元素的情况，把array[i...mid]的元素依次拷贝到temp；
• 第二个额外循环（while(j<=high)）：专门处理第二个子数组还有剩余元素的情况，把array[j...high]的元素依次拷贝到temp。

举个实际例子：
如果第一个子数组是[1,3,5]，第二个是[2,4]，第一个while循环会依次取1、2、3、4，此时i变成3（超过mid=2），循环停止。这时候第一个子数组还剩5，第一个额外循环就会把5补到temp里，最终temp就是完整的有序数组[1,2,3,4,5]。
反过来，如果第一个子数组是[2,4]，第二个是[1,3,5]，第一个循环取1、2、3、4后，j变成3（超过high=4？不对，这里high应该是4，j到3时第二个子数组还剩5），第二个额外循环就会把5补进去，确保数组完整。

这两个循环是分别处理两种不同的剩余场景，少了任何一个都会导致部分元素丢失，合并后的数组不完整。

二、如何正确测试打印第一个while循环后的结果？ #

你用display()函数出现奇怪结果，主要是两个原因：

1. display()是遍历全局的array数组，但此时merge函数还没把临时数组temp的内容拷贝回原数组，array还是未完全排序的状态；
2. display()用的是全局变量n，而merge当前处理的只是某个子数组（low到high范围），用全局n打印整个数组自然会出现无关内容。

正确的做法是在merge函数里，直接打印临时数组temp中已经处理好的部分，或者打印两个子数组的剩余元素。比如，在第一个while循环结束后，添加这段测试代码：

// 打印第一个while循环后已排序的temp片段
cout << "After first while loop, sorted temp part: ";
for (int idx = low; idx < k; idx++) {
    cout << temp[idx] << " ";
}
cout << endl;

// 打印第一个子数组剩余的元素
cout << "Remaining elements in first subarray (" << i << " to " << mid << "): ";
for (int idx = i; idx <= mid; idx++) {
    cout << array[idx] << " ";
}
cout << endl;

// 打印第二个子数组剩余的元素
cout << "Remaining elements in second subarray (" << j << " to " << high << "): ";
for (int idx = j; idx <= high; idx++) {
    cout << array[idx] << " ";
}
cout << endl;

这样你就能清晰看到：

• 第一个循环已经处理好的有序元素；
• 哪一个子数组还有剩余元素；
• 剩余元素的具体内容，也就直观明白为什么需要后面的两个while循环来补全了。

另外提醒下，不要在merge函数里调用display()，它的作用是打印最终排序完成的整个数组，并不适合用来查看中间子数组的处理过程。

备注：内容来源于stack exchange，提问作者Margret Mauno