python - python中的递归合并排序

我正在尝试使用python中的两个函数进行合并排序。但是我收到了像
一样的错误 每当运行我的代码时， IndexError：列表分配索引超出范围。我不知道哪一部分是错的。
这是我的代码。 任何帮助都会欣赏!!

def merge(A):

    def merge_sort(A,first,last):
        if first<last:
            mid=(first last)//2
            merge_sort(A,first, mid)
            merge_sort(A,mid 1,last)

            temp=[]
            temp.append(99999)
            i=first
            j=mid 1
            k=0
            while i<=mid and j<=last:
                if A[i]<=A[j]:
                    temp[k]=A[i]
                    k=k 1
                    i=i 1
                else:
                    temp[k]=A[j]
                    k=k 1
                    j=j 1
            while i<=mid:
                temp[k]=A[i]
                k=k 1
                i=i 1
            while j<=last:
                temp[k]=A[j]
                k=k 1
                j=j 1
            a=0
            b=first
            while a<k:
                A[b]=temp[a]
                b=b 1
                a=a 1

    merge_sort(A,0,len(A)-1)

    return A

最佳答案：

1 个答案:

答案 0 :(得分：1)

只要此元素不存在，您就无法为temp[k]分配值。

删除行temp.append(99999)，将每个temp[k]=A[i]替换为temp.append(A[i])，将每temp[k]=A[j]替换为temp.append(A[j])。

你最终会得到：

def merge(A):

    def merge_sort(A,first,last):
        if first<last:
            mid=(first last)//2
            merge_sort(A,first, mid)
            merge_sort(A,mid 1,last)

            temp=[]
            i=first
            j=mid 1
            k=0
            while i<=mid and j<=last:
                if A[i]<=A[j]:
                    temp.append(A[i])
                    k=k 1
                    i=i 1
                else:
                    temp.append(A[j])
                    k=k 1
                    j=j 1
            while i<=mid:
                temp.append(A[i])
                k=k 1
                i=i 1
            while j<=last:
                temp.append(A[j])
                k=k 1
                j=j 1
            a=0
            b=first
            while a<k:
                A[b]=temp[a]
                b=b 1
                a=a 1

    merge_sort(A,0,len(A)-1)

    return A


A = [1,9,4,5]
print(A)
print(merge(A))

输出：

[1, 9, 4, 5]
[1, 4, 5, 9]