如何找到MergeSort算法最坏情况排列 修复对应Python代码递归内存错误

现有代码核心错误 #

• 语法错误：join函数末尾残留了enter code here无效字符，会直接触发语法报错
• 索引逻辑错误：split、join函数没有针对当前处理的子数组区间[l, r]做偏移，全量使用数组起始索引，导致递归过程中数组访问越界、递归深度无限增加，最终触发递归错误、内存溢出
• 拆分逻辑错误：split函数中i*2的取值逻辑没有适配子数组偏移，不符合归并最坏排列的生成规则，正确逻辑是将有序数组的元素交替分配到左、右子数组，保证归并时每次都需要做元素比较

修复后可运行的实现 #

def join(A, left, right, l):
    # 合并左右子数组到原数组的l起始位置
    i = 0
    # 先填左子数组
    while i < len(left):
        A[l + i] = left[i]
        i += 1
    # 再填右子数组
    j = 0
    while j < len(right):
        A[l + i] = right[j]
        i += 1
        j += 1

def split(A, left, right, l, r):
    # 交替拆分当前子数组[l, r]的元素到左右数组
    for i in range(len(left)):
        left[i] = A[l + 2*i]
    for i in range(len(right)):
        right[i] = A[l + 2*i + 1]

def generateWorstCase(A, l, r):
    if r - l <= 0:
        return
    mid = (l + r) // 2
    left = [0]*(mid - l + 1)
    right = [0]*(r - mid)
    split(A, left, right, l, r)
    generateWorstCase(left, 0, len(left)-1)
    generateWorstCase(right, 0, len(right)-1)
    join(A, left, right, l)

# 测试用例
arr = [1, 2, 3, 4, 5, 6, 7, 8]
generateWorstCase(arr, 0, len(arr)-1)
print(arr) # 输出 [1, 5, 3, 7, 2, 6, 4, 8] 即为符合要求的最坏排列

额外优化建议 #

• 避免重复创建数组：可以提前开辟全局的临时数组空间，递归过程中复用，减少频繁申请释放内存的开销，处理大数组时性能提升明显
• 非递归实现：如果需要处理长度超过Python默认递归深度（默认1000）的数组，可以把递归实现改写成迭代版本，彻底避免递归深度限制问题
• 边界适配：如果输入数组长度不是2的整数次幂，可添加边界判断逻辑，适配任意长度数组的最坏排列生成

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