归并排序mid值如何设置？求助排查代码部分输入异常问题

嘿，我来帮你捋捋问题出在哪！你的归并排序代码部分输入正常、部分抛出异常，核心问题其实不是mid的赋值（不过mid确实有更严谨的写法），而是mergeArr函数里temp数组的索引使用错误，另外逆序数的计算也有小问题，下面详细说：

一、先解决导致异常的核心错误 #

你在mergeArr里定义了int temp[r-l+1];，这个数组的长度是r-l+1，索引范围是0到r-l，但你把k初始化为l，然后执行temp[k++] = ...——这直接就数组越界了！

举个例子，当递归处理输入1 3 5 2 4 6的右半部分（l=3, r=5，对应元素2、4、6）时，temp的长度是3，索引只能到2，但k从3开始赋值，这肯定会触发内存访问异常，这就是你遇到问题的根源。

另外还有个小问题：你计算逆序数的inv_count += (mid - i);是错的，正确的应该是inv_count += (n1 - i);，因为L数组的长度是n1，当L[i] > R[j]时，L中从i到末尾的所有元素都和R[j]构成逆序，不过这个不影响排序结果，只是逆序数统计不准。

修正后的mergeArr函数如下：

void mergeArr(int a[], int l, int mid, int r) {
    int n1 = mid - l + 1;
    int n2 = r - mid;
    int i, j, k;
    int inv_count = 0;
    int temp[r-l+1];
    int L[n1], R[n2];
    
    for(i = 0; i < n1; i++)
        L[i] = a[l + i];
    for(j = 0; j < n2; j++)
        R[j] = a[mid + j + 1];
    
    i = j = 0;
    // temp的索引从0开始，不是l！
    k = 0;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j])
            temp[k++] = L[i++];
        else {
            temp[k++] = R[j++];
            // 修正逆序数计算
            inv_count += (n1 - i);
        }
    }
    
    while(i < n1)
        temp[k++] = L[i++];
    while(j < n2)
        temp[k++] = R[j++];
    
    // 将temp的内容复制回原数组的l到r区间
    for(i = 0; i < k; i++)
        a[l + i] = temp[i];
}

二、归并排序中mid值的正确设置方式 #

你当前写的mid = (l + r)/2在大多数场景下能工作，但有个潜在的坑：当l和r都是极大的整数时，l + r可能会超出int类型的取值范围，导致整数溢出，算出错误的mid值。

更安全、更严谨的写法是：

mid = l + (r - l) / 2;

这种写法先计算r-l的差值（不会溢出，因为r >= l），再除以2，最后加上l，结果和(l+r)/2完全一致（整数除法向下取整），但彻底避免了溢出风险。

另外要确认划分逻辑：归并排序中mid的作用是把数组分成[l, mid]和[mid+1, r]两个子数组，你mergeSort里的递归调用mergeSort(a,l,mid);和mergeSort(a,mid+1,r);是完全正确的，只要mid计算没问题，这个划分就不会出错。

把这些问题修正后，你的归并排序应该就能处理所有输入了！

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