在递归循环中为合并排序创建后键入
我试图通过自己编写算法来理解算法。 在尝试复制合并排序时，我遇到了一些麻烦：left＆right return none-type，并在第一个while循环中为len（左）引发错误。 我一直在与代码战斗，无法弄清楚我错过了什么？ 它不应该只是循环，直到左右列表的大小减少到1，这将允许他们离开if循环并继续下一部分的功能？
def merge_sort(A):
if len(A) < 2:
return A
else:
mid= len(A)//2
left= merge_sort(A[:mid])
right= merge_sort(A[mid:])
i = j = 0
sortedlist = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
sortedlist.append(left[i])
i+=1
else:
sortedlist.append(right[j])
j+=1
while i < len(left):
sortedlist.append(left[i])
i+=1
while j < len(right):
sortedlist.append(right[j])
j+=1
print(str(sortedlist))
所有你需要做的就是添加一个return语句（下面代码中的最后一条语句）：
def merge_sort(A):
if len(A) < 2:
return A
else:
mid= len(A)//2
left = merge_sort(A[:mid])
right = merge_sort(A[mid:])
i = j = 0
sortedlist = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
sortedlist.append(left[i])
i+=1
else:
sortedlist.append(right[j])
j+=1
while i < len(left):
sortedlist.append(left[i])
i+=1
while j < len(right):
sortedlist.append(right[j])
j+=1
# NEED TO RETURN THE LIST HERE!
return sortedlist
如果你的函数没有返回任何类似left = merge_sort(A[:mid])语句，它将把None分配给left而不是排序后的（一半）列表。
你可以用以下方法测试：
import random
lst = list(range(15))
random.shuffle(lst)
ret = merge_sort(lst)
print(ret)
你的函数不包含return语句。 您应该在最后添加return sortedlist 。