归并排序中统计逆序数代码报错：TypeError: object of type 'NoneType' has no len() 问题排查求助

我来帮你拆解问题，你的代码存在两个核心问题，一个是触发TypeError的直接原因，另一个是逆序数统计的逻辑错误：

1. 为什么会触发object of type 'NoneType' has no len()？ #

你的merge_sort函数在处理长度≥2的列表时没有返回值，导致递归调用时返回None。举个例子：当你执行left = merge_sort(list[:middle])，如果list[:middle]的长度≥2，merge_sort会进入else分支，但分支末尾没有任何return语句，所以left会被赋值为None。后续把left传入merge函数时，调用len(left)自然就会抛出这个类型错误。

2. 逆序数统计逻辑的错误 #

你当前的count +=1是在left[i] < right[j]时执行，这完全不符合逆序数的定义。逆序数是指「左侧元素大于右侧元素的对数」，当right[j] < left[i]时，左侧从i到末尾的所有元素都比right[j]大，每一个都和right[j]构成一个逆序对，所以此时应该累加len(left) - i，而不是加1。

修复后的完整代码 #

def merge(left, right):
    result = []
    i, j = 0, 0
    count = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # 用<=避免重复元素被误统计为逆序
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            # 此时left[i..末尾]的所有元素都比right[j]大，逆序数增加len(left)-i
            count += len(left) - i
            j += 1
    # 直接extend剩余元素，简化代码
    result.extend(left[i:])
    result.extend(right[j:])
    return result, count

def merge_sort(arr):
    if len(arr) < 2:
        # 长度小于2的列表没有逆序对，返回原数组和0
        return arr, 0
    middle = len(arr) // 2
    # 递归获取左右子数组的排序结果和内部逆序数
    left, left_count = merge_sort(arr[:middle])
    right, right_count = merge_sort(arr[middle:])
    # 合并时统计跨左右的逆序数
    merged, merge_count = merge(left, right)
    # 总逆序数 = 左子数组逆序数 + 右子数组逆序数 + 合并产生的逆序数
    total_count = left_count + right_count + merge_count
    return merged, total_count

# 测试示例
sorted_arr, inversion_count = merge_sort([2,3,9,2,9])
print("排序后的数组:", sorted_arr)
print("逆序数:", inversion_count)  # 正确结果是2：(2,2)、(3,2)

修复关键点总结 #

• 给merge_sort补充了返回值：每次递归返回排序后的数组和对应的逆序数，确保上层调用能拿到有效的列表，不会出现None。
• 修正了逆序数统计逻辑：在right[j] < left[i]时累加len(left)-i，准确统计合并阶段产生的跨左右逆序对。
• 总逆序数是三个部分的和：左子数组内部的逆序数、右子数组内部的逆序数、合并时产生的跨左右逆序数，这是归并排序统计逆序数的标准思路。

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