关于归并排序代码中第三个while循环升序构建原理的咨询

要搞懂这个while (p2 <= right)循环的作用，得先回顾归并排序的核心逻辑：先递归拆分并排序左右两个子数组，再将两个已排序的子数组合并成一个有序数组。

我们拆解合并阶段的三个while循环来看：

1. 第一个while循环：双指针同步合并 #

while (p1 <= mid && p2 <= right)
{
    if (arr[p1] < arr[p2])
        sorted[idx++] = arr[p1++];
    else
        sorted[idx++] = arr[p2++];
}

这个循环的作用是同时遍历左右两个已排序的子数组，每次挑选较小的元素放入sorted数组，直到其中一个子数组的元素被完全遍历完为止。

它会在两种情况下停止：

• 左子数组遍历完毕：p1 > mid
• 右子数组遍历完毕：p2 > right

2. 第三个while循环：处理右子数组剩余元素 #

while (p2 <= right)
    sorted[idx++] = arr[p2++];

这个循环专门处理左子数组已经遍历完，但右子数组还有剩余元素的情况。

为什么可以直接把剩余元素依次放入sorted？
因为左右两个子数组本身已经是有序的了——在进入合并阶段前，递归调用mergesort已经把它们各自排好序。当左子数组的元素全部被放入sorted后，右子数组剩下的元素必然都大于等于sorted中已有的所有元素，而且它们自身也是升序排列的，所以直接按顺序追加到sorted后面就能保证整体有序。

举个具体例子 #

假设：

• 左子数组（left到mid）：[1, 3, 5]
• 右子数组（mid+1到right）：[2, 4, 6, 7]

第一个循环的执行过程：

1. 比较1和2 → 取1放入sorted，p1移到3，idx加1
2. 比较3和2 → 取2放入sorted，p2移到4，idx加1
3. 比较3和4 → 取3放入sorted，p1移到5，idx加1
4. 比较5和4 → 取4放入sorted，p2移到6，idx加1
5. 比较5和6 → 取5放入sorted，p1超出mid（左子数组遍历完），第一个循环停止

此时右子数组还剩6和7，第三个循环就会把这两个元素依次追加到sorted的末尾，最终sorted变成[1,2,3,4,5,6,7]，完全有序。

简单说，这个循环就是**“扫尾”**——把右子数组没处理完的剩余有序元素，直接补到合并后的数组里，确保所有元素都被正确合并。

内容的提问来源于stack exchange，提问作者이민영