基于归并排序统计i<j且arr[i]<=arr[j]配对数的代码调试求助

核心错误原因 #

你的代码核心问题出在merge_count函数的配对计数逻辑：

• 归并排序拆分的左半数组A、右半数组B的所有元素，原始下标天然满足「A中元素下标 < B中元素下标」的条件，所以跨左右的合法配对数仅需要统计A[x] <= B[y]的组合数即可，和两个遍历指针i、j的差值没有任何关系，你使用的(j-i)+1公式完全没有逻辑支撑。
• 你没有利用A、B都是升序排列的特性做批量计数，导致计数结果完全偏离预期。

修正方案 #

利用A、B的有序性优化计数逻辑：因为两个数组都是升序，当A[i] <= B[j]时，B数组中从j到末尾的所有元素都大于等于A[i]，所以当前A[i]可以贡献len(B) - j个合法配对，累加后移动A的指针；否则移动B的指针即可。

修正后完整代码如下：

def merge_count(A, B):
    res = []
    pairs = 0
    i, j = 0, 0
    
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            # 批量统计B中所有 >= A[i]的元素数量
            pairs += len(B) - j
            res.append(A[i])
            i += 1
        else:
            res.append(B[j])
            j += 1
    
    # 剩余元素直接合并，不需要再计数
    res.extend(A[i:])
    res.extend(B[j:])
        
    return pairs, res

def sort_count(nums):
    if len(nums) <= 1:
        return 0, nums
    mid = len(nums) // 2
    pL, nL = sort_count(nums[:mid])
    pR, nR = sort_count(nums[mid:])
    p_cross, merged = merge_count(nL, nR)
    return pL + pR + p_cross, merged

可选简化方案 #

如果你更熟悉逆序对的统计逻辑，也可以用「总合法i<j配对数 - 逆序对数量」得到结果，总配对数计算公式为len(nums) * (len(nums) - 1) // 2，逻辑更不容易出错。

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