合并排序混淆中的递归调用

Question

代码如下：

def mergeSort(myList):
    if len(myList) > 1:
        mid = len(myList) // 2
        left = myList[:mid]
        right = myList[mid:]

        # Recursive call on each half
        mergeSort(left)
        mergeSort(right)

        # Two iterators for traversing the two halves
        i = 0
        j = 0
        
        # Iterator for the main list
        k = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
              # The value from the left half has been used
              myList[k] = left[i]
              # Move the iterator forward
              i += 1
            else:
                myList[k] = right[j]
                j += 1
            # Move to the next slot
            k += 1

        # For all the remaining values
        while i < len(left):
            myList[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            myList[k]=right[j]
            j += 1
            k += 1

myList = [2,4,1,5,3]
mergeSort(myList)
print(myList)

我的疑问是调用了 mergeSort(left) 和 mergeSort(right) 函数，但没有 return 语句，那么列表的顺序如何改变，改变后的列表如何 return返回函数没有return statement.Ps:我还是个初学者所以请尽量为我简化它谢谢

Answer 1

no return statement is there so how is the order of the list changing

在对 myList[k] 进行赋值的每个实例中都会对其进行更改。由于这确实是调用者提供给您的函数的列表，因此调用者会注意到对其值的任何更改。

调用者不会知道函数是否会为myList本身分配一个新值（就像myList = []），但是当它是mutated (with myList[k] = ...) 然后这个 mutates 调用者列表。函数和调用者正在访问 same 列表。

how is the changed list even returned back

它没有return退回。这就是就地排序所做的：该函数不会创建一个新列表来按排序顺序将值复制到其中——在这种情况下，它必须 return 表示给来电者的列表。不，使用就地排序，列表本身中的值会四处移动，影响调用者拥有的 one 列表。

因此在函数运行完成后，调用者可以检查列表并看到它现在已排序。

混合情况

现在，对于典型的合并排序，会创建其他临时列表，但它们仅用于预留一些值，但它们确实会移回调用者的列表中，之后这些临时列表就会过时。

例如，这里使用给定列表中值的副本创建了两个新列表：

left = myList[:mid]
right = myList[mid:]

这些都是通过递归调用变异（排序）的：

mergeSort(left)
mergeSort(right)

但是函数的其余部分专门用于将值从（已排序的）left 和 right 列表复制到调用者的列表 (myList) 中，以便在结束 left 和 right 不再需要，myList 被排序。

合并排序混淆中的递归调用

Recursive call in merge sort confusion

python

algorithm

mergesort

混合情况