归并排序算法中逆序计数器的正确放置位置咨询

你的merge函数里的逆序计数器位置和逻辑完全不正确，核心问题出在这些地方：

• 计数时机错误：当left[l] < right[r]时，这两个元素不构成逆序对，此时统计属于无效操作，会产生错误的计数结果。
• 计数逻辑低效且错误：就算在正确时机，你的while循环写法会漏数（比如temp1 < left.size() - 1会漏掉左半部分最后一个元素），而且逐个遍历计数会把归并排序O(n log n)的时间复杂度拖成O(n²)，对于10万级别的数组来说性能会严重下降。
• 相等元素处理缺失：当left[l] == right[r]时，既没处理左半部分元素的放置，也忽略了这类元素不构成逆序对的规则，会导致排序逻辑和计数逻辑都出现问题。

正确的逆序对计数逻辑 #

归并排序统计逆序对的核心是：当右半部分的right[r]小于左半部分的left[l]时，左半部分中从l到末尾的所有元素都和right[r]构成逆序对，直接累加leftSize - l即可，无需逐个遍历。

修正后的merge函数 #

void merge(vector<int> &left, vector<int> &right, vector<int> &array, int &inversionCount) 
{
    int leftSize = left.size();
    int rightSize = right.size();
    int i = 0, l = 0, r = 0;

    while (l < leftSize && r < rightSize)
    {
        if (left[l] <= right[r])
        {
            // 左元素小于等于右元素，无逆序对，直接放入结果数组
            array[i] = left[l];
            i++;
            l++;
        }
        else
        {
            // 右元素更小，左半部分从l到末尾的所有元素都与right[r]构成逆序对
            inversionCount += leftSize - l;
            array[i] = right[r];
            i++;
            r++;
        }
    }

    // 处理左半部分剩余元素，这些元素已和右半部分所有元素完成比较，无需额外计数
    while (l < leftSize)
    {
        array[i] = left[l];
        i++;
        l++;
    }
    
    // 处理右半部分剩余元素，同样无需计数
    while (r < rightSize)
    {
        array[i] = right[r];
        i++;
        r++;
    }
}

额外说明 #

• 使用left[l] <= right[r]是为了保证排序的稳定性，同时严格遵循逆序对定义（仅统计i<j且a[i]>a[j]的情况，相等元素不算逆序对）。
• 修正后的逻辑保持了归并排序O(n log n)的时间复杂度，完全适配10万级别的数组处理需求。

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