C++用归并排序统计数组逆序对输出错误，求代码问题排查

你提交的归并排序实现逆序对计数的代码存在一处逻辑错误，位于merge函数的逆序对计数计算行：

count += (mid - i);

这行的计算逻辑不正确。因为i是左子数组leftArray的局部下标，当leftArray[i] > rightArray[j]时，左子数组中从i到末尾的所有元素都比当前rightArray[j]大，每个元素都可以和当前右元素组成逆序对，因此正确的计数应该加上左子数组剩余的元素总数n1 - i，而非用原数组中点mid和i计算。

修正后完整代码 #

#include <vector>
using namespace std;
int merge(vector<int>& nums, int start, int mid, int end){
    int count = 0;
    int n1 = mid - start + 1;
    int n2 = end - mid;
    vector<int> leftArray(n1);
    vector<int> rightArray(n2);
    for(int i = 0; i < n1; i++){
        leftArray[i] = nums[start + i];
    }
    for(int i = 0; i < n2; i++){
        rightArray[i] = nums[mid + 1 + i];
    }
    int i = 0, j = 0, k = start;
    while(i < n1 && j < n2){
        if(leftArray[i] <= rightArray[j]){
            nums[k++] = leftArray[i++];
        }
        else{
            nums[k++] = rightArray[j++];
            // 修正此处的计数逻辑
            count += (n1 - i);
        }
    }
    while(i < n1){
        nums[k++] = leftArray[i++];
    }
    while(j < n2){
        nums[k++] = rightArray[j++];
    }
    return count;
}

int mergeSort(vector<int>& nums, int start, int end){
    if(start >= end) return 0;
    int count = 0;
    
    int mid = (start + end) / 2;
    count +=  mergeSort(nums, start, mid);
    count += mergeSort(nums, mid + 1, end);
    count += merge(nums, start, mid, end);
    return count;
}

int countInversions(vector<int>& nums) {
    return mergeSort(nums, 0, nums.size() - 1);
}

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