Python中归并排序（MergeSort）出现索引越界（index out of range）错误求助

嘿，我瞅了你的归并排序代码，一下子就找到问题所在啦！

你遇到的索引越界错误，根源是这行代码：

s=merge(a,lower,middle,upper,[])

你给merge传了一个空列表[]当临时数组b，但在merge函数里你直接用b[k] = a[i]这种方式赋值——空列表根本没有对应的索引位置啊，这不就直接触发index out of range了嘛！

另外还有个隐藏问题：就算你修复了上面的错误，你的排序结果最后也不会生效，因为mergesort里没有把合并好的临时数组内容同步回原数组a里。

我给你改好了代码，你看看：

def merge(a, lower, middle, upper, b):
    i = lower
    j = middle + 1
    k = lower
    while(i <= middle and j <= upper):
        if(a[i] <= a[j]):
            b[k] = a[i]
            i = i + 1
        else:
            b[k] = a[j]
            j = j + 1
        k = k + 1
    if(i > middle):
        while(j <= upper):
            b[k] = a[j]
            j = j + 1
            k = k + 1
    elif(j > upper):
        while(i <= middle):
            b[k] = a[i]
            i = i + 1
            k = k + 1
    # 把临时数组里的排序结果同步回原数组
    for idx in range(lower, upper + 1):
        a[idx] = b[idx]

def mergesort(a, lower, upper):
    if(lower < upper):
        middle = (lower + upper) // 2
        mergesort(a, lower, middle)
        mergesort(a, middle + 1, upper)
        # 创建和原数组长度一致的临时数组，避免索引越界
        b = [0] * len(a)
        merge(a, lower, middle, upper, b)

# 测试一下
arr = [1,3,2,7,11,10]
mergesort(arr, 0, 5)
print(arr)  # 会输出 [1, 2, 3, 7, 10, 11]

主要改了这两处：

• 在mergesort里创建了和原数组长度相同的临时数组b，这样merge里通过索引赋值就不会有越界问题了
• 在merge函数末尾加了循环，把临时数组里合并好的部分复制回原数组，确保排序结果能被保留下来

备注：内容来源于stack exchange，提问作者maths and chess