Python归并排序切片实现触发递归深度超限错误的原因是什么？

你遇到的递归报错核心原因是修改代码后错误覆盖了原入参变量A的值，具体逻辑如下：

• 你计算分界值m时，使用的是刚进入merge_sort函数时原始入参A的长度，此时切片A[:m]和A[m:]的长度之和等于原始A的长度，递归到最后必然能触发len(A)==1的终止条件。
• 修改为你写的两行代码后，第一行A = merge_sort(A[0:m])直接把原变量A覆盖为了前半段切片排序后的结果，此时新的A的长度只有m，远小于原始A的长度。
• 第二行执行B = merge_sort(A[m:])时，m的取值还是基于原始入参长度计算的结果，远大于当前新A的长度，因此A[m:]会得到空列表。
• 空列表传入merge_sort后，永远无法命中len(A)==1的终止条件，就会陷入无限递归，最终触发递归深度超限的报错。

我们可以用你的测试用例直观验证：
调用merge_sort([6,7,2])时，原始入参长度为3，m=floor(3/2)=1：

1. 第一行执行A = merge_sort(A[:1])，排序后得到新的A = [6]，长度为1
2. 第二行执行A[m:]即[6][1:]，得到空列表
3. 空列表传入merge_sort后，长度为0不满足终止条件，计算m=floor(0/2)=0，继续调用merge_sort(A[:0])也就是空列表，无限递归触发报错。

你只需要避免覆盖原始入参A即可，参考写法：

def merge_sort(A):
    if len(A) == 1:
        return A
    m = floor(len(A) / 2)
    # 用独立变量存储左右段排序结果，不修改原A
    left = merge_sort(A[:m])
    right = merge_sort(A[m:])
    return merge(left, right)

内容的提问来源于stack exchange，提问作者AK-CHP