归并排序递归函数返回排序列表与计数时报TypeError错误求助

错误原因分析 #

当你将subordinates函数的返回值改为(sorted_list, count)后，出现类型错误的核心原因有两点：

• 递归返回类型不匹配：修改后，递归调用subordinates得到的结果是包含排序子列表和计数的元组，而非原代码中的纯列表。但merge函数仍然期望接收两个列表作为参数，导致merge内部访问L1[i]和L2[j]时，实际操作的是元组的元素（元组第一个元素是子列表，第二个是整数计数），当循环到元组的第二个元素时，就会出现整数与列表的非法比较，触发TypeError。
• Base Case未同步修改：原代码中列表长度≤1时直接返回列表，与修改后的元组返回类型不一致，导致递归层级中返回类型混乱，进一步加剧错误。

解决方案 #

方案1：基于全局计数的修改 #

保留全局count变量，同步修改递归逻辑和Base Case，从递归返回的元组中提取排序子列表传给merge：

count = 0
def merge(L1,L2):
    m = len(L1)
    n = len(L2)
    i = 0 
    j = 0 
    c = []
    
    while i<m and j<n:
        if L1[i]<=L2[j]:
            c.append(L1[i])
            i += 1
        else:
            c.append(L2[j])
            j += 1
    while i<m:
        c.append(L1[i])
        i += 1
    while j<n:
        c.append(L2[j])
        j += 1
    return c

def subordinates(L):
    length = len(L)
    global count 
    count = count + 1    
        
    if length <= 1:
        return (L, count)  # Base Case改为返回元组，保持类型一致
    
    # 递归调用后提取元组中的排序子列表
    L1_tuple = subordinates(L[:length//2])
    L2_tuple = subordinates(L[length//2:])
    sorted_list = merge(L1_tuple[0], L2_tuple[0])  # 传入子列表而非元组

    return (sorted_list, count)

x = [10, 33, 45, 67, 92, 100, 5, 99, 105]
result = subordinates(x)
print("排序后的列表:", result[0])
print("函数调用次数:", result[1])

方案2：移除全局变量（推荐） #

全局变量容易引发副作用，更优雅的方式是通过递归传递计数，每个递归分支独立计算调用次数：

def merge(L1,L2):
    m = len(L1)
    n = len(L2)
    i = 0 
    j = 0 
    c = []
    
    while i<m and j<n:
        if L1[i]<=L2[j]:
            c.append(L1[i])
            i += 1
        else:
            c.append(L2[j])
            j += 1
    # 简化剩余元素的追加逻辑
    c.extend(L1[i:])
    c.extend(L2[j:])
    return c

def subordinates(L):
    length = len(L)
    
    if length <= 1:
        return (L, 1)  # 长度≤1时，当前调用次数为1
    
    # 递归获取子列表和对应调用计数
    L1, count1 = subordinates(L[:length//2])
    L2, count2 = subordinates(L[length//2:])
    sorted_list = merge(L1, L2)
    
    # 总计数 = 两个子问题的计数 + 当前调用的1次
    total_count = count1 + count2 + 1
    return (sorted_list, total_count)

x = [10, 33, 45, 67, 92, 100, 5, 99, 105]
sorted_x, call_count = subordinates(x)
print("排序后的列表:", sorted_x)
print("函数调用总次数:", call_count)

内容的提问来源于stack exchange，提问作者Ravi Teja Avasarala