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

Question

我是python3的新手，正在尝试《算法导论》一书中所写的合并排序算法。我有下面的代码，它在中途正常工作，但由于某种原因在接近尾声时失败了。我尝试在调用merge()函数之前和之后放入一些基本的调试语句。我的猜测是，这与标记子数组开始和结束的索引有关，但我不知道具体是什么。我在各种各样的列表上分别测试了函数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