Python 3.5无return递归函数原理及归并排序实现疑问

嘿，我完全理解你的困惑——递归函数居然不需要return就能完成排序，这乍一看确实有点反直觉！咱们结合你给出的代码，一步步拆解它的工作原理，你就能豁然开朗了。

核心关键：Python列表是可变对象 #

首先得记住一个Python基础知识点：列表是可变对象。当你把一个列表传入函数时，函数拿到的是这个列表的引用，而不是它的副本。所以函数内部对列表的修改，会直接影响到外部的原列表。这个归并排序实现就是利用了这一点，根本不需要return返回结果，而是直接修改传入的原列表。

代码逻辑分步拆解 #

咱们把这段mergeSort代码拆成「拆分」和「合并」两个阶段来看：

1. 递归拆分阶段 #

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort(lefthalf)  # 递归处理左半部分
        mergeSort(righthalf) # 递归处理右半部分

这部分的作用是把大列表不断拆分成更小的子列表，直到子列表的长度为1（因为单个元素本身就是有序的）。比如你传入一个[5,3,8,6]，会被拆成[5,3]和[8,6]，然后[5,3]再拆成[5]和[3]，以此类推。

2. 原地合并阶段 #

当递归到最底层（子列表长度为1）后，程序会开始执行拆分之后的while循环（你代码里没写完完整的合并逻辑，我补全了剩余部分）：

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

这时候lefthalf和righthalf已经是排好序的子列表了（因为递归已经把它们拆到最小并完成了合并）。咱们把这两个有序子列表的元素逐个比较，按从小到大的顺序放回原列表alist的对应位置。

因为alist是上层调用传入的列表的引用，所以这里的修改会直接同步到上层的列表中。比如当合并[5]和[3]时，原列表是[5,3]，合并后会被改成[3,5]，这个修改会被上层的mergeSort调用感知到。

举个直观的小例子 #

假设我们调用mergeSort([3,1,2])，整个流程是这样的：

1. 第一次调用：拆分[3,1,2]为[3]和[1,2]
2. 递归处理[3]：长度不大于1，跳过拆分，直接进入合并阶段（没有循环，啥也没做）
3. 递归处理[1,2]：拆分[1,2]为[1]和[2]
   • 处理[1]：啥也没做
   • 处理[2]：啥也没做
   • 合并[1]和[2]：把原列表[1,2]（其实就是上层的righthalf）保持为[1,2]
4. 回到最上层，合并[3]和[1,2]：把原列表[3,1,2]修改为[1,2,3]

你看，整个过程没有return，全靠修改原列表的引用完成排序！

和带return的归并排序对比 #

很多归并排序的实现会采用返回新列表的方式，比如：

def mergeSort(alist):
    if len(alist) <=1:
        return alist
    mid = len(alist)//2
    left = mergeSort(alist[:mid])
    right = mergeSort(alist[mid:])
    # 合并left和right，返回新的排序列表
    merged = []
    i=j=0
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            merged.append(left[i])
            i+=1
        else:
            merged.append(right[j])
            j+=1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

这种写法需要return，因为它是创建新列表返回，而你的代码是直接修改原列表，所以不需要return。

内容的提问来源于stack exchange，提问作者Paweł Kozielski-Romaneczko