我的C++归并排序代码输出错误，逐行对比仍无法定位问题

看起来你在实现归并排序时遇到了结果不正确的问题，逐行对比参考代码也没找到问题——这种情况往往是一些容易忽略的细节（比如索引、循环边界）在搞鬼。先把你提供的代码片段整理出来：

我参考了一份代码实现归并排序，但运行后输出结果错误。我逐行对比了参考代码，却仍无法找到问题所在。我的代码如下：

#include <iostream>
using namespace std;
void printA(int a[] , int l , int r){
    cout << endl;
    for(int i = l ; i < r ; i++)
        cout<< a[i] <<" ";
    cout<< endl;
}
void merge(int arr[] , int l , int m , int r){
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1];
    int R[n2];
    for(int i=0 ; i < n1 ; i++)
        L[i]=arr[l+i];
    for(int j=0 ; j < ...

接下来我会列出几个归并排序实现中最容易踩坑的点，结合你的代码片段逐一分析：

1. 未完成的右半部分拷贝循环 #

你提供的代码里，拷贝右半部分到R数组的循环只写了一半，正确的写法应该是：

for(int j=0 ; j < n2 ; j++)
    R[j] = arr[m + 1 + j];

这里要注意右半部分的起始索引是m+1，而不是m——因为左半部分是l到m（共n1=m-l+1个元素），右半部分自然从m+1开始到r（共n2=r-m个元素）。如果这里写错，会导致右半部分的元素拷贝错误，直接影响排序结果。

2. 合并阶段的索引与循环边界错误 #

假设你已经完成了左右数组的拷贝，接下来的合并步骤也很容易出错：

• 合并时要同时遍历L和R数组，条件应该是i < n1 && j < n2（而不是<=）
• 当其中一个数组遍历完后，要把另一个数组剩下的元素全部拷贝回原数组，这部分的循环条件也要注意边界
• 原数组的填充索引应该从l开始，而不是从0开始，否则会覆盖前面已经排好序的元素

正确的合并循环示例：

int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
    } else {
        arr[k] = R[j];
        j++;
    }
    k++;
}
// 拷贝L数组剩余元素
while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
}
// 拷贝R数组剩余元素
while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
}

3. 打印函数的范围问题 #

你的printA函数中，循环条件是i < r，这意味着如果你的数组长度是n，调用printA(arr, 0, n)才能打印所有元素（因为索引从0到n-1）。如果调用时传的是printA(arr, 0, n-1)，会漏掉最后一个元素，可能让你误以为排序结果错误。

4. 递归调用的边界问题 #

归并排序的递归函数（你没贴出来，但必须有）需要正确划分左右区间：

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // 避免溢出，替代(l+r)/2
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

这里的关键是：左半部分是l到m，右半部分是m+1到r，如果把右半部分写成m到r，会导致区间重叠或遗漏元素。

建议你先补全未完成的循环，然后检查上述几个细节点，应该就能找到问题所在了。

内容的提问来源于stack exchange，提问作者S4rt-H4K