归并排序（MergeSort）无法完成数组排序，求排查问题根源

你的代码核心问题出在merge函数中，处理剩余元素的两个while循环被错误地嵌套在了主合并循环的内部。

错误分析 #

在原代码的merge函数里，当进入while(i<n1 && j<n2)的循环体后，每执行一次元素比较赋值，就会立刻触发两个剩余元素的循环，把其中一个子数组的剩余元素全部写入原数组，直接打断了正常的交替合并逻辑。这导致合并过程完全没有按照归并排序的规则交替选取两个子数组的最小元素，自然无法完成正确排序。

修正后的代码 #

只需要把两个处理剩余元素的while循环移到主合并循环的外面即可：

#include <iostream>
using namespace std;

void merge(int arr[], int l, int mid, int r)
{
    int n1 = mid - l + 1;
    int n2 = r - mid;

    int array1[n1];
    int array2[n2];

    for(int i = 0; i < n1; i++)
    {
        array1[i] = arr[l + i];
    }

    for(int i = 0; i < n2; i++)
    {
        array2[i] = arr[mid + 1 + i];
    }

    int i = 0; int j = 0; int k = l;

    // 主合并循环：交替取两个子数组的最小元素
    while(i < n1 && j < n2)
    {
        if(array1[i] < array2[j])
        {
            arr[k] = array1[i];
            i++; k++;
        }
        else
        {
            arr[k] = array2[j];
            j++; k++;
        }
    }

    // 处理第一个子数组的剩余元素
    while(i < n1)
    {
        arr[k] = array1[i];
        i++; k++;
    }

    // 处理第二个子数组的剩余元素
    while(j < n2)
    {
        arr[k] = array2[j];
        j++; k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int mid = (l + r) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

int main()
{
    int arr[] = {5,4,3,2,1};

    mergeSort(arr, 0, 4);
    for(int i = 0; i < 5; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

补充说明 #

原代码中缺少标准输入输出头文件#include <iostream>和命名空间声明using namespace std;，修正后的代码已补上，确保程序能正常编译运行。

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