关于归并排序中子数组合并逻辑的疑问

问题描述 #

我从GeeksforGeeks拿到下面这段Python归并排序代码，搞不懂子数组的排序逻辑：递归排序左、右子数组后再合并，为啥不会出问题？我本来以为代码里一直初始化子数组，合并时用的是未排序的版本。

举个例子：输入数组input_array = [7,1,4,3,5,2,9,8]，递归调用流程是mergeSort([7,1,4,3])→mergeSort([7,1])→mergeSort([7])→mergeSort([1])，排序[7,1]得到[1,7]；接着处理右半部分mergeSort([4,3])→mergeSort([4])→mergeSort([3])，排序[4,3]得到[3,4]。

我困惑的点在于：当排序[7,1,4,3]时，代码会比较左右子数组，但我觉得之前排好序的子数组已经被栈丢弃了，当前栈帧里的L还是[7,1]、R还是[4,3]，根本没更新？我肯定漏了指针、原地排序或者栈调用的细节，但就是想不通原因。

代码片段 #

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        mergeSort(L)
        mergeSort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 处理剩余元素
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

核心解惑：Python列表是可变对象，递归修改会同步到当前栈帧 #

你搞错了最关键的一点：Python里的列表是可变对象，当你调用mergeSort(L)时，函数内部对L的修改（也就是排序）会直接作用于当前栈帧里的L变量，而不是产生一个新的、独立的副本丢到栈里不管。

具体到你的例子：

• 当执行mergeSort([7,1])时，函数里的L是[7]，R是[1]。递归到最底层后，合并这两个子数组，会把当前栈帧里的[7,1]直接改成[1,7]——这个修改是实时的，上层调用mergeSort([7,1,4,3])里的L变量，就是这个已经排好序的[1,7]。
• 同理，mergeSort([4,3])执行完后，上层调用里的R变量已经变成了排好序的[3,4]。
• 所以当回到mergeSort([7,1,4,3])的合并步骤时，L和R已经是排好序的[1,7]和[3,4]，合并后自然会得到正确的[1,3,4,7]，再把这个结果写回上层的数组里。

补充细节：不是纯原地排序，但子数组的修改会同步 #

这段代码不是纯原地排序——它通过切片创建了L和R两个子数组副本，但因为列表是可变对象，递归排序L和R时，修改的就是当前栈帧里的L和R本身。等递归返回后，这两个变量已经是排好序的状态，接下来的合并步骤就是把这两个有序子数组的内容写回原数组arr的对应位置。

简单说：递归调用mergeSort(L)不是白跑的，它会把你当前手里的L给排好序，直接存在原地，供后续合并使用。

内容的提问来源于stack exchange，提问作者Solruhama