我一直在Python/c++中实现归并排序(来自interactivepython)。代码完全工作，但我的问题是，我似乎不能弄清楚为什么代码的特定部分实际上是工作的。
代码是:
def mergeSort(alist):
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i<len(lefthalf) and j<len(righthalf):
if lefthalf[i]<righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i<len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j<len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
plist = [54,26,93,17]
mergeSort(plist)
print(plist)
在lefthalf =[54 26]之后，进一步的子程序拆分为lefthalf =[54]和righthalf =[26]，合并代码提供了list =[26, 54](这是排序好的左半部分)。
现在我在调试窗口中执行的下一步，我得到了lefhalf =[26,54]。这是怎么可能的，因为第一次调试显示它之前定义为[54,26]。对[26,54]的更新发生在哪里?
任何帮助将是超级感激!
您的mergesort函数修改您传递给它的列表。也就是说，它更改内容，使项按顺序排列，而不是返回一个新的列表。
这是你在调试器中看到的，在递归调用期间。在递归的第一层，通过复制原始列表中的一些值(使用切片语法)来创建lefthalf。它开始含有[54, 26]。然后将该列表传递给mergesort的另一个调用。注意，命名可能会令人困惑，因为在内部调用中，它将列表引用为alist(并且它有自己单独的lefthalf列表)。当内部调用返回时，外部调用的lefthalf的内容被修改为[26, 54](它们是有序的，这正是我们想要的!)。
可能是你的调试器没有弄清楚何时发生返回。因为它们都是同一个函数(由于递归)，当内部调用结束，外部调用的控制流恢复时，可能不太明显。
下面是您的代码演练，其中我展示了在对示例列表排序时递归的各个级别中不同变量的值。请注意，这不是可运行的Python代码，我缩进是为了表明递归的级别，而不是为了控制流。为了使示例相对简短，我还省略了一些步骤，例如在合并过程中比较两个子列表中的值以及更新i、j和k索引:
plist = [54,26,93,17]
mergesort(plist)
# alist is a referece to plist which contains [54,26,93,17]
lefthalf = alist[:mid] # new list which initially contains [54,26]
righthalf = alist[mid:] # new list which initially contains [93,17]
mergesort(lefthalf)
# alist is a reference to the outer lefthalf list, which contains [54,26]
lefthalf = alist[:mid] # new list, initially contains [54]
righthalf = alist[mid:] # new list, initially contains [26]
mergesort(lefthalf)
# alist is a reference to the previous level's lefthalf, [54]
# the if statement doesn't pass its test, so we do nothing here (base case)
# lefthalf was not changed by the recursive call
mergesort(righthalf)
# alist is a reference to the previous level's righthalf, [26]
# base case again
# righthalf was not changed
alist[k]=righthalf[j] # now we merge lefthalf and righthalf back into alist
alist[k]=lefthalf[i] # these statements change the contents of alist
# lefthalf's contents changed, it is now sorted, [26,54]
mergesort(righthalf)
# alist is a reference to the outer righthalf list, which contains [93,17]
lefthalf = alist[:mid] # new list, initially contains [93]
righthalf = alist[mid:] # new list, initially contains [17]
mergesort(lefthalf) # base case, nothing happens (I'll skip the details)
mergesort(righthalf) # base case, nothing happens
alist[k]=righthalf[j] # merge lefthalf and righthalf back into alist
alist[k]=lefthalf[i] # we change the contents of alist to [17,93]
# righthalf's contents changed, it is now sorted, [17,93]
alist[k]=righthalf[j] # merge lefthalf and righthalf back into alist (more steps)
alist[k]=lefthalf[i]
alist[k]=lefthalf[i]
alist[k]=righthalf[j] # after these statements, alist is [17,26,54,93]
# plists's contents are changed so it contains [17,26,54,93]
这可能会帮助您从复杂的递归情况中退一步，看看一个更简单的例子，以确保您理解列表是如何变化的:
a = [1, 2] # create a list object with some initial contents
b = a # b refers to the same list object as a, nothing is copied
b[1] = 3 # this modifies the list object itself, replacing the 2 with a 3
print(a) # prints [1, 3] even through we're looking at a rather than b
def func(lst): # lst will be a new name bound to whatever is passed to the function
lst[1] = 4 # we can modify that passed-in object (assuming it's the right type)
func(a) # lst in the function will become another name for the list object
print(a) # prints [1, 4]
python中的列表在函数内部是可变的(即它们的内容可以改变)。当在函数内部更改列表时，更改将发生在调用该函数的列表上，因为它们是同一个列表。
因此，对列表的更新发生在每次操作alist或alist的切片时，无论是在第一次调用中还是在任何递归调用中。
编辑:删除误导位