python：合并排序没有按预期工作？

Question

我是 python3 的新手，正在尝试 'Introduction to Algorithms' 书中写的归并排序算法。我有以下代码，它在中途正常工作但由于某种原因在最后失败了。我尝试在调用 merge() 函数之前和之后放置一些基本的调试语句。我的猜测是它与标记子数组开始和结束的 indices 有关，但我无法弄清楚到底是什么。我在各种列表中分别测试了函数 merge()，以确保它在 mergesort()

中使用之前可以正常工作

from math import inf
from random import randint

def merge(A, p, q, r): 
    L = A[p:q+1]
    R = A[q+1:r+1]
    L.append(inf)
    R.append(inf)
    i = 0
    while L[0] is not inf or R[0] is not inf:
        if L[0] < R[0]:
            A[i] = L.pop(0)
        else:
            A[i] = R.pop(0)
        i += 1

def mergesort(A, p, r):
    if p < r:
        q = (p+r)//2
        mergesort(A, p, q)
        mergesort(A, q+1, r)
        print('merging:', A[p:q+1], 'and', A[q+1:r+1])
        merge(A, p, q, r)
        print('after merging:', A[p:r+1])
     
z =[randint(-100, 100) for x in range(5)]
print('before:', z)
mergesort(z, 0, len(z)-1)
print('after:', z)

这是初始列表的一些输出 [92, 79, -8, 89, -83]

before: [92, 79, -8, 89, -83]
merging: [92] and [79]
after merging: [79, 92]
merging: [79, 92] and [-8]
after merging: [-8, 79, 92] 
merging: [89] and [-83] <----- okay, alright upto this point...
after merging: [89, -83] <-- ?? goes all wrong from this point...
merging: [-83, 89, 92] and [89, -83]
after merging: [-83, 89, -83, 89, 92]
after: [-83, 89, -83, 89, 92]

感谢任何帮助。谢谢！

Answer 1

问题是 merge 没有合并所有 A，而是 A 的一部分。所以A的第一个索引需要是p，而不是0。只需更改：

    i = 0

至：

    i = p

这是整个函数：

def merge(A, p, q, r): 
    L = A[p:q+1]
    R = A[q+1:r+1]
    L.append(inf)
    R.append(inf)
    i = p
    while L[0] is not inf or R[0] is not inf:
        if L[0] < R[0]:
            A[i] = L.pop(0)
        else:
            A[i] = R.pop(0)
        i += 1

python：合并排序没有按预期工作？

python: Merge sort not working as intended?

python

algorithm

mergesort