为什么归并排序是“最稳”的排序？用整理两副扑克牌的方式讲透它 - 每日分享

你有没有经历过这样的场景：面前摊着两堆已经按从小到大排好的扑克牌，你需要把它们合并成一整副有序的牌。通常你会做的是——同时看两堆的最上面一张，哪张小就先拿哪张，直到其中一堆空了，再把另一堆直接摞上去。

这个动作，就是归并排序的核心。而整个归并排序，不过是在反复做这件事：先把一整副牌拆成单张，再两两合并成有序的整副。听起来简单，但正是这个朴素的思路，让归并排序成了所有排序算法里“脾气最好”的一个——无论数据是正序、倒序还是乱序，它都稳稳地跑在 O(n log n)。

分治：拆到不能再拆，再拼回去

归并排序的精髓是四个字：分而治之。把一个大问题拆成若干小问题，逐个解决，再合并结果。

给你一个乱序数组：[38, 27, 43, 3, 9, 82, 10]。归并排序做的第一件事不是“排序”，而是切：

从中间切成两半：[38, 27, 43, 3] 和 [9, 82, 10]
每半再切，一直切到每个子数组只剩一个元素

为什么要切到只剩一个？因为一个元素天然就是有序的。这是递归的“基准情况”，也是整个算法的信心来源。

然后开始合并，比如先合并 [38] 和 [27]，比较两个元素，27 小，先放 27，再放 38，得到 [27, 38]。接着继续合并更大的有序块，每一轮合并都像整理扑克牌一样，比较两堆的“牌头”，把小的依次取出。

这个过程画成图，就是一棵倒立的二叉树：顶部是完整数组，底部是 n 个单元素节点，然后再一层层合并上去。每一层合并的总工作量是 O(n)，而树的高度是 log₂(n)，所以总复杂度稳定在 O(n log n)。

代码：核心就两步

归并排序的代码结构非常清晰，核心就两个函数：一个负责合并两个有序列表，一个负责递归拆分。

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

短短十几行，但有几个关键细节值得玩味。

第一，为什么 merge 最后的两个 extend 必不可少？
因为 while 循环的退出条件是“有一边空了”，但另一边可能还剩几个元素。这些剩余元素本身就是有序的，而且都大于已放入结果的所有元素，直接拼上去就行。如果漏掉这一步，列表会变短，数据直接丢失。这是新手最容易踩的坑。

第二，递归基为什么用 <= 1 而不是 == 1？
因为空数组也是有序的。如果你写 == 1，当传进来一个空列表时，递归就会出错——它进不了基情况，会尝试继续切分，切出来还是空，导致无限递归。用 <= 1 一次性兜住两种边界情况，代码更稳健。

第三，merge_sort 必须返回合并后的列表。
递归的每一层都要把结果向上传递，如果有一个分支忘记 return，上一层的 merge 拿到的就是 None，程序直接崩溃。这类 bug 在递归里非常常见，但只要记住“递归函数每一层都要有返回值”就够了。

一道题看懂它的时间底线

我在讲归并排序的时候，经常让学生做一道选择题：

归并排序在最坏情况下的时间复杂度是？ A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)

正确答案是 B。很多同学会犹豫，因为他们刚学完快速排序，知道快排最坏是 O(n²)，于是想当然地以为归并排序也有“最坏”一说。

但归并排序不一样。它的分解和合并过程完全不受数据排列方式的影响——无论数组是否已经有序，它都得先切到最小，再合并回去。每一层合并都要处理 n 个元素，层数是 log₂(n)，所以最好、最坏、平均全是 O(n log n)。这就是它“稳”的第一层含义：时间复杂度稳定，不会因为输入数据而产生性能悬崖。

选 D 的同学是误把“分解的层数”当成了总复杂度。没错，分治确实有 log n 层，但每一层都要合并所有元素，所以不能只算高度，还要乘以每层的 n。这个误区值得单独拎出来讲清楚。

再聊“稳定性”：它到底稳定在哪里

另一个常见考点是判断这句话对不对：

归并排序是一种稳定的排序算法。

对，但这背后有前提：在合并时，当两个元素相等，必须先把左边子数组的元素放入结果。

比如合并 [a:3, b:3] 和 [c:2]（这里用字母表示原始顺序），如果左子数组是 [3, 3]，右子数组是 [2]，合并时先取出 2，然后左边两个 3 依次取出，顺序保持为 a, b。因为你总是先取左边的，相等元素的相对顺序自然被保留。

如果实现时脑子一抽，写成 left[i] <= right[j]，或者反过来优先取右边，那相等元素的顺序就可能被打乱，稳定性就被破坏了。这也是为什么我会强调：稳定性不是算法的抽象属性，而是具体实现中的行为约束。归并排序的“稳”，靠的是你写代码时的那一个比较符号。

这种稳定性的价值在哪里？典型场景是“按成绩排，成绩相同按学号排”。你可以先按学号排序，再用归并排序按成绩排一次，成绩相同的人会保持学号从小到大的相对顺序。换成不稳定的快速排序，这一步就会翻车。

代价：用空间换稳

归并排序不是没有缺点。它每次合并都要创建新的列表存放结果，额外空间是 O(n)。不像快速排序可以在原数组上通过交换完成，归并排序需要的是“另起炉灶”。

在内存充裕的场合，这不算问题。但在嵌入式设备或处理超大文件的场景，O(n) 的额外空间可能就是致命的。这也是为什么外部排序（比如对硬盘上无法一次装入内存的数据排序）会采用归并排序的变体——它只需要有限的内存分块读取，就能完成整个排序。

从归并排序出发，你能走得更远

归并排序是分治思想的经典代表。学会它，你等于拿到了一把钥匙：理解递归的分层结构，理解合并时的指针移动，理解“先解决子问题再汇总”的思维模式。

下一步可以对比学习快速排序——同样是分治，但一个先处理后合并，一个先拆分后处理，两者对照能加深你对递归过程的理解。然后可以去看归并排序的迭代写法，或者用它解决“求逆序对”的问题——归并排序在合并时天然能统计逆序对的数量，这是它另一处巧妙的应用。

就像搭积木：先把大积木拆成小积木，再把小积木按规则拼回去。归并排序教会我们的，从来不只是排序本身，而是一种“拆分-解决-合并”的思维方式。这种思维，比任何一行代码都值钱。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）