合并排序问题，代码在递归过程中是错误的

Question

我正在研究合并排序，它是用递归过程编写的，但它不正确，我打印每个程序

import math
def merge_sort(A):
l=len(A)
if l>1:
merge_sort(A[:math.floor(l/2)])
merge_sort(A[math.floor(l/2):])
merge(A)
def merge(A):
l=len(A)
half1=A[:math.floor(l/2)]
half2=A[math.floor(l/2):]
l1=len(half1)
l2=len(half2)
B=[]
for i in range(l):
if l1 == 0:
B.append(half2[len(half2)-l2])
l2-=1
elif l2 == 0:
B.append(half1[len(half1)-l1])
l1-=1
elif half1[len(half1)-l1] <= half2[len(half2)-l2]:
B.append(half1[len(half1)-l1])
l1-=1
elif half2[len(half2)-l2] < half1[len(half1)-l1]:
B.append(half2[len(half2)-l2])
l2-=1
for i in range(l):
A[i]=B[i]
print(A)
A=[5,3,2,8,6,7,11,9,111,3]
merge_sort(A)

为了找到错误的地方，我打印出每一步，这给了我

[3, 5]
[6, 8]
[2, 8, 6]
[2, 5, 3, 8, 6]
[7, 11]
[3, 111]
[9, 111, 3]
[7, 9, 11, 111, 3]
[5, 3, 2, 7, 8, 6, 11, 9, 111, 3]

Answer 1

Slicing提供了一个新的数组，因此递归merge_sort调用没有到位(即对输入数组本身(。因此，对输入数组没有执行任何操作。

要进行演示，请考虑以下片段：

a = [1, 2, 3]
b = a[:]
b[0] = 0
assert a[0] == b[0] # raise AssertionError

此外，还有更多错误：您需要在merge_sort中返回新排序的子列表，然后在merge中将它们一起返回(接受两个列表，而不是只有一个参数(。我建议一行一行地看完说明书，然后再试一次。