C++归并排序程序输出错误，请求代码问题排查

嘿，我帮你找到了代码里导致输出异常的几个关键问题，咱们一个个来看：

1. 归并阶段的数组索引错误（最核心问题） #

在Sort函数的最后一个while循环里，你不小心把arr2[j]写成了arr2[i]：

// 错误代码
while(j<n2){ arr[it]=arr2[i];j++;it++; }

当执行到这个循环时，i已经遍历完arr1并超出了它的范围，此时用i去访问arr2会触发数组越界，读取到内存里的随机垃圾值，这就是你输出里出现32696、802952496这类奇怪数字的原因。

修正后应该是：

while(j<n2){ arr[it]=arr2[j];j++;it++; }

2. 递归函数中mid的位置逻辑不严谨 #

你把mid的计算放在了if(low<high)的外面：

void MergeSort(int* arr,int low,int high)
{
    int mid=low+(high-low)/2; // 这里
    if(low<high)
    {
        MergeSort(arr,low,mid);
        // ...
    }
}

当递归到单个元素（low >= high）时，计算mid完全是多余的，虽然不会直接引发错误，但不符合代码逻辑规范，应该把mid的定义移到if块内部：

void MergeSort(int* arr,int low,int high)
{
    if(low<high)
    {
        int mid=low+(high-low)/2; // 移到这里
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Sort(arr,low,mid,high);
    }
}

3. 数组中的八进制字面量问题 #

你在main函数的数组里写了011，在C++中，以0开头的整数会被解析为八进制数，011转换成十进制是9。如果你的本意是输入十进制的11，那这里要去掉前面的0；如果就是要输入9，那这个写法没问题，但容易混淆，建议直接写9更清晰。

修正后的完整代码 #

#include <iostream>
#include <algorithm>
using namespace std;

void Sort(int *arr,int low,int mid,int high) //Sorting algo
{
    int n1=mid-low+1,n2=high-mid;
    int arr1[n1];
    int arr2[n2];
    for(int i=0;i<n1;i++)arr1[i]=arr[i+low];
    for(int j=0;j<n2;j++)arr2[j]=arr[mid+j+1];
    int i=0,j=0,it=low;
    while(i<n1 && j<n2)
    {
        if(arr1[i]<=arr2[j])
        {
            arr[it]=arr1[i];i++,it++;
        }
        else
        {
            arr[it]=arr2[j];j++,it++;
        }
    }
    while(i<n1){ arr[it]=arr1[i];i++;it++; }
    while(j<n2){ arr[it]=arr2[j];j++;it++; } // 修正索引错误
}

void MergeSort(int* arr,int low,int high) //Recursive Merge Function
{
    if(low<high)
    {
        int mid=low+(high-low)/2; // mid移至if内部
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Sort(arr,low,mid,high);
    }
}

int main()
{
    // 把011改成9，和你描述的输入一致
    int arr[]={4,2,6,1,9,5,6,78,9,34,74,86,14,3,0};
    int n=sizeof(arr)/sizeof(arr[0])-1; // 此处正确，数组索引范围为0~14
    MergeSort(arr,0,n);
    for(int a:arr)
    {
        cout<<a<<" ";
    }
    return 0;
}

运行修正后的代码，输出就会是正确的排序结果：0 1 2 3 4 5 6 6 9 9 14 34 74 78 86

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