我写了一个合并排序函数，并认为我已经完成了......但在赋值中它说该函数应该对实际列表进行排序而不是创建副本(所以我认为按值而不是引用调用？现在，它不起作用，因为列表本身没有更改。
def mergeSort(L, ascending = True):
print('Mergesort, Parameter L:')
print(L)
result = []
if len(L) == 1:
return L
mid = len(L) // 2
teilliste1 = mergeSort(L[:mid], ascending)
teilliste2 = mergeSort(L[mid:], ascending)
x, y = 0, 0
while x < len(teilliste1) and y < len(teilliste2):
if (ascending and teilliste1[x] > teilliste2[y]) or (not ascending and teilliste1[x] < teilliste2[y]):
result.append(teilliste2[y])
y = y + 1
else:
result.append(teilliste1[x])
x = x + 1
result = result + teilliste1[x:]
result = result + teilliste2[y:]
return result
liste1 = list([3, 2, -1, 9, 17, 4, 1, 0])
mergeSort(liste1)
print(liste1) # result will be the unsorted list
我需要在函数中更改什么才能使其按值调用并对实际列表进行排序？
我知道我能做到
mergeResult = mergeSort(liste1)
print(mergeResult)
但显然我必须更改原始参数列表。
编写递归分解函数有两种基本方法。不可变版本在两个较小部分的副本上调用自身，然后重新组装并返回它们;这就是你写的。可变版本在实际输入上调用自身，然后就地修改该输入，并且不返回任何内容;这就是你的老师在这里想要的。
请注意，与其他一些排序算法不同，mergesort 不能使用常量的额外存储来完成，只能比线性额外存储更好。(对数是可能的，但很复杂;我怀疑你的老师坚持这一点。正因为如此，您在书籍、维基百科等中找到的大多数合并排序算法都将被编写为复制排序而不是就地排序。这意味着这可能是一个"技巧问题"，试图看看您是否可以弄清楚如何从算法的众所周知的复制版本转换为具有显式额外存储的就地版本。
你总是可以编写一个不可变的算法，然后在最后发生变异，例如：
def _mergesort(L, ascending):
# your existing code
def mergesort(L, ascending=True):
L[:] = _mergesort(L, ascending)
这为您提供了不变性的所有成本，而没有好处。但这确实意味着你可以使用相同的 API 编写各种排序函数，如果这是一个合理的优化，这些函数都是就地实现的，但如果不是，则不会，这似乎是你的老师所追求的。
如果您不想要包装器函数，则可以将最后一行从：
return result
。自：
L[:] = result
但是，由于这会更改 API，因此还需要更改递归调用以匹配。例如，您可以执行以下操作：
teilliste1 = L[:mid]
mergeSort(teilliste1, ascending)
teilliste2 = L[mid:]
mergeSort(teilliste2, ascending)
在 Python 中，变异递归分解函数通常通过将开始和结束索引与列表一起向下传递来工作，如下所示：
def mergesort(L, ascending=True, start=None, stop=None):
if start is None: start = 0
if stop is None: stop = len(L)
if stop - start <= 1:
return
mid = (stop - start) // 2 + start
mergeSort(L[start:mid], ascending)
mergeSort(L[mid:stop], ascending)
# etc.
如上所述，合并步骤将需要一些辅助存储。最简单的事情——对于你的作业来说可能已经足够好了，即使这意味着线性空间——就是建立一个左列表和一个右列表，然后将它们重新分配到L[start:mid], L[mid:stop] = left, right。
请注意，这与上面的L[:] = result版本并没有太大区别;实际上只是在过程的前半部分使用L本身以及开始和停止索引来代替副本，然后在合并过程中仅在最后复制。