归并排序递归实现的原地修改疑问：为何无需显式赋值？

首先明确：你手上的这段代码根本没有做原地修改，所谓“效果如同赋值给left_half和right_half”，是因为混淆了「返回新数组的归并实现」和「原地归并实现」的逻辑。

核心逻辑拆解 #

归并排序常见有两种实现思路：

• 一种是真正的原地排序：需要借助辅助数组，通过索引操作直接修改原数组的元素位置，这种实现复杂度高，日常很少用到。
• 另一种是返回新数组的递归实现：这正是你手上代码的逻辑，每一层递归都会生成新的子数组，排序后返回全新的有序数组，完全不会修改输入的原数组。

假设你的代码结构类似这样（以Python为例）：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = arr[:mid]  # 生成原数组的切片副本，不是原数组本身
    right_half = arr[mid:]
    a = merge_sort(left_half)  # 递归返回排序后的新数组，赋值给a
    b = merge_sort(right_half) # 同理，返回排序后的新数组给b
    return merge(a, b)  # 合并两个有序新数组，返回最终结果

• 调用merge_sort(left_half)时，函数处理的是left_half的副本（切片操作arr[:mid]会创建新数组），递归完成后返回的是全新的有序数组，赋值给变量a。原left_half其实完全没被修改，只是后续合并用的是a而非原left_half，所以看起来像是left_half被排序了。
• 同理，变量b接收的是right_half排序后的新数组，原right_half始终保持初始的未排序状态。

为什么会产生“原地修改”的错觉？ #

因为整个递归链条的最终结果是返回合并后的有序新数组，上层递归拿到的是这个有序结果，而你没有去打印原left_half/right_half的状态。如果在代码里加一行print(left_half)，你会发现它还是最初的未排序切片，根本没被修改。

总结 #

你的代码没有任何原地修改操作，所有排序都是在新创建的子数组上完成的，a、b只是接收了递归返回的有序新数组，最终合并得到结果。所谓“效果如同赋值”，只是因为你使用了返回的新数组，而非原变量本身被修改。

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