Merge Sort算法处理小列表正常，大列表崩溃求助

核心问题定位 #

你的问题大概率是递归分支未正确返回排序后的子列表。短列表（长度≤4）可能刚好触发基准条件（len(arr)<=1）直接返回，掩盖了递归调用未返回值的问题；当列表更长时，深层递归分支因缺少返回语句，导致sorted_right被赋值为None。

具体排查与修复步骤 #

1. 检查merge_sort函数的递归返回逻辑
   确保每次递归调用merge_sort时，都将结果赋值给sorted_left/sorted_right，且函数始终返回合并后的结果。错误示例与正确写法对比：

   • 错误写法（缺少递归结果赋值/返回）：

     def merge_sort(arr):
         if len(arr) <= 1:
             return arr
         mid = len(arr)//2
         left = arr[:mid]
         right = arr[mid:]
         merge_sort(left)  # 未将递归结果赋值给变量
         merge_sort(right)
         return merge(left, right)  # 直接用原未排序的左右列表
     

   • 正确写法：

     def merge_sort(arr):
         if len(arr) <= 1:
             return arr
         mid = len(arr)//2
         left = arr[:mid]
         right = arr[mid:]
         sorted_left = merge_sort(left)  # 接收递归返回的有序子列表
         sorted_right = merge_sort(right)
         return merge(sorted_left, sorted_right)  # 合并有序子列表并返回
     

2. 验证merge函数的返回逻辑
   确认merge函数在所有分支都有返回值：当其中一个子列表遍历完毕时，要将另一个子列表的剩余元素追加后返回，避免出现无返回值的情况。比如：

   def merge(left, right):
       result = []
       i = j = 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])
               j += 1
       # 追加剩余元素
       result.extend(left[i:])
       result.extend(right[j:])
       return result  # 确保始终返回结果
   

3. 调试定位
   在递归调用后添加打印语句，观察sorted_left和sorted_right的取值：

   sorted_left = merge_sort(left)
   sorted_right = merge_sort(right)
   print(f"sorted_left: {sorted_left}, sorted_right: {sorted_right}")
   

   当输出中出现None时，即可定位到对应的递归分支未正确返回。

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