如果让我只挑一个排序算法推荐给刚开始学算法的朋友我会毫不犹豫选归并排序。倒不是因为它的代码最好写——恰恰相反很多人在第一次接触递归版归并时都会被那个“先拆再合”的过程绕晕但只要你真正把归并排序吃透“分治”这两个字就不再是教科书上的抽象概念而是长在你身体里的一种思维习惯。后面再去看快速排序、二分查找、甚至在磁盘上做大规模数据排序都会顺畅很多。这篇文章我打算从归并排序的核心思想开始一路讲到递归实现、迭代实现、链表归并、外部排序再到我实际写代码时踩过的边界条件和调试心得。内容尽量说人话代码可以直接抄走跑起来。适合正在准备算法面试的人、工作中需要对大量数据排序的工程师以及任何一个想知道“为什么归并排序能稳定做到 O(n log n)”的读者。1. 归并排序到底解决什么问题1.1 一个朴素问题两堆有序的牌怎么合成一堆先忘掉代码想一个生活场景。你手上有两叠扑克牌分别都已经按从小到大排好了现在要把它们合成一整叠依然从小到大。你会怎么做正常人不会把所有牌混在一起重新排序而是同时看两叠牌最上面各是哪张谁小谁就先拿出来放到新牌堆里。拿完一张那叠牌就往上翻一张直到其中一堆空了再把另一堆剩下的牌直接接上去。整个过程每张牌只需要被比较一次时间是线性的。这个操作就是归并排序里“治”的核心步骤术语叫 merge。归并排序的全部秘密本质上就是反复使用这个简单的牌堆合并动作。1.2 分治策略的落地拆到不能再拆为止归并排序的整体思路可以概括成一句话先把一个大数组从中间切成两半左半边和右半边各自排序然后把两个有序半段合并起来。问题来了左半边和右半边各自怎么排序答案还是同样的办法继续从中间切、递归地排直到每一段只剩下一个元素。一个元素算不算有序当然算它没有邻居不存在逆序问题。当递归拆到这个粒度时就开始一层层向上做 merge两个长度为 1 的有序段合成一个长度为 2 的有序段两个长度为 2 的合成长度为 4一路合并回去最终整个数组有序。很多初学者会困惑为什么一定要拆到只剩一个元素才开始合并能不能在中间提前停下来可以而且工程里确实会这样做后面我会讲“小数组阈值”这个优化。但为了把原理讲清楚先接受“拆到 1”这个最纯粹的形式它能让递归结构变得非常整齐。1.3 稳定性归并排序容易被忽略的隐藏优点排序算法的“稳定性”是指如果两个元素的值相等排序后它们的相对顺序会不会改变。稳定排序会保持原来的先后关系不稳定排序则可能颠倒。归并排序天然是稳定的。原因很简单在 merge 时如果左边元素和右边元素相等我们规定总是先把左边的放进结果数组。这样一来原来在前的元素合并后依然在前。这个特性在真实业务里太重要了——比如先按时间排序再按优先级排一次序如果第二次排序不稳定时间上的先后关系就可能被打乱。我在工作中遇到过不止一次因为排序不稳定导致订单列表顺序错乱的事故而凡是切换到稳定排序的场景问题立刻消失。2. 递归版归并执行过程逐层拆解2.1 先看最直观的写法切片版我用 Python 写一个最适合理解归并思想的教学版本def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i j 0 result [] 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这个版本的优点是逻辑和原理一一对应数组切一半递归排排完合并。但不建议在生产环境直接这么写因为切片会复制数组每一层递归都在产生新列表空间开销成倍增加。它只适合用来理解算法、写笔试题答案、或者给完全没接触过归并的人做演示。2.2 一次 merge 的走指针模拟把 merge 单独拿出来用具体数据走一遍。假设 left [3, 7, 9]right [1, 4, 8]。比较 left[0] 3 和 right[0] 11 更小把 1 放入结果j 变成 1。 比较 left[0] 3 和 right[1] 43 更小把 3 放入结果i 变成 1。 比较 left[1] 7 和 right[1] 44 更小把 4 放入结果j 变成 2。 比较 left[1] 7 和 right[2] 87 更小把 7 放入结果i 变成 2。 比较 left[2] 9 和 right[2] 88 更小把 8 放入结果j 变成 3。 right 已经被取完直接把 left 剩余的 [9] 接在结果后面。最终结果 [1, 3, 4, 7, 8, 9]。整个过程里每个元素被比较的次数不确定但总体比较次数不会超过两个数组长度之和。这个性质非常关键它是归并排序时间复杂度 O(n log n) 的地基。2.3 复杂度推导为什么任何输入都是 O(n log n)归并排序的时间复杂度可以用一个递推关系表达。把大小为 n 的数组排序的时间记为 T(n)它等于排左半边 T(n/2) 加排右半边 T(n/2)再加上一次 merge 的代价merge 两个各 n/2 的数组最多比较 n 次所以T(n) 2T(n/2) O(n)这个递推式展开来可以用递归树看得很清楚。第一层有一个规模为 n 的问题merge 代价是 n第二层有两个规模为 n/2 的问题每个 merge 代价是 n/2合计 n第三层有四个规模 n/4 的问题合计代价还是 n。每一层的合并总代价都是 n而数组不断对半切总层数是 log2(n)所以总复杂度是 n 乘以 log2(n)即 O(n log n)。归并排序最迷人的地方在于不管输入是已经排好的、完全逆序的、还是随机打乱的它的比较次数都差不多始终是 O(n log n)。这一点快排做不到快速排序在极端情况下会退化到 O(n²)但归并排序不会。代价是它需要额外的数组空间。2.4 空间开销哪些地方容易被忽略归并排序的空间复杂度常被简化说成 O(n)但严格讲递归版本的空间是 O(n log n)。O(n) 来自 merge 时临时申请的数组O(log n) 来自递归调用栈。为什么是 log n因为递归深度等于数组被对半切的次数也就是 log2(n)。教学版代码里的切片操作会让空间更差——每一层递归都产生新的切片数组虽然同一时刻不是所有层都同时存在但总空间消耗会明显大于 O(n)。我用 Python 讲过很多次课每次都会强调不要用教学版直接处理大数组。工程化的写法应该复用同一个临时数组把空间真正压到 O(n)下面这部分就是干这个的。3. 从“能跑”到“能上生产”代码细节与边界3.1 避免切片用临时数组原地归并的写法生产环境推荐的是基于下标区间和全局临时数组的版本。核心思路是归并时先把区间内容复制到临时数组再从临时数组逐个比较写回原数组。def merge_sort_inplace(arr): n len(arr) tmp [0] * n _merge_sort(arr, 0, n, tmp) def _merge_sort(arr, left, right, tmp): if right - left 1: return mid (left right) // 2 _merge_sort(arr, left, mid, tmp) _merge_sort(arr, mid, right, tmp) # 归并 [left, mid) 和 [mid, right) 两个区间 tmp[left:right] arr[left:right] i, j, k left, mid, left while i mid and j right: if tmp[i] tmp[j]: arr[k] tmp[i] i 1 else: arr[k] tmp[j] j 1 k 1 while i mid: arr[k] tmp[i] i 1 k 1这里有几个细节值得单独说。区间写法我用了左闭右开 [left, right)这样mid (left right) // 2之后左半是 [left, mid)右半是 [mid, right)分割非常干净不容易出现 1/-1 错位问题。为什么只处理左边剩余的部分不用处理右边剩余因为右半部分的元素在 tmp 和 arr 中是同一个位置我们先把 arr 复制到了 tmp再把结果写回 arr如果右边还有剩余它们已经待在正确位置上不需要再动。复用同一个 tmp 数组很关键。每次递归都新建临时数组会让空间复杂度退化为 O(n log n)大数据量时内存消耗会很吓人。3.2 用迭代替代递归自底向上的非递归实现递归版有一个实际负担递归深度是 log n虽然不大但在一些内存受限的嵌入式环境或者递归栈深度被严格限制的平台上仍然可能出问题。这时可以用自底向上的迭代版先把数组看成 n 个长度为 1 的有序段然后两两合并成长度为 2 的段再四四合并直到整个数组合并完毕。def merge_sort_iter(arr): n len(arr) tmp [0] * n width 1 while width n: for left in range(0, n, 2 * width): mid min(left width, n) right min(left 2 * width, n) if mid right: tmp[left:right] arr[left:right] i, j, k left, mid, left while i mid and j right: if tmp[i] tmp[j]: arr[k] tmp[i] i 1 else: arr[k] tmp[j] j 1 k 1 while i mid: arr[k] tmp[i] i 1 k 1 width * 2 return arr迭代版的边界条件比递归版更容易写错。最典型的是 mid 和 right 的计算当数组末尾不足一个完整段时mid 或 right 要用 min 夹紧到 n否则会访问到数组外面的元素。另一个容易忽略的点是if mid right这个判断如果某一段在末尾只剩下左半部分没有右半部分可以合并直接跳过就行这段本身已经有序。3.3 边界条件的几个典型翻车现场我整理了自己写归并时踩过的几个坑几乎每个都能在网上看到别人问同样的问题。第一个坑奇数长度数组的切分。比如长度 5 的数组mid 2左半 [0,2)右半 [2,5)。左半长度 2、右半长度 3合并没问题。但如果你用某个早期的教学写法把区间搞成 [left, mid] 和 [mid1, right]在这种奇数长度下很容易漏掉或重复元素。闭区间的 1/-1 调整非常容易出错我后来统一改用左闭右开世界清净了。第二个坑merge 结束后忘了把剩余元素拷回去。递归版最底下那个while i mid循环很多人会漏掉。如果漏了你会发现排序结果“好像差不多对了但又少了点什么”这是因为左边剩余元素没被写回它们在 tmp 里的值被直接丢弃了。第三个坑tmp 数组一次性复制整个区间。有人为了让代码简洁直接把整个 arr 复制到 tmp再在整个数组范围上做归并。这在大数组上会多做很多无意义的赋值操作性能下降明显。正确做法是只复制当前需要合并的区间 [left, right)。4. 工程中的取舍归并排序何时不可替代4.1 数组对象排序与外部排序归并的主场面试算法题里归并排序常常被快速排序抢风头但在真实工程里归并排序的地位远比表面看起来重要。原因有两个稳定性和对外部存储的友好性。稳定性这一点前面已经说过业务排序几乎都要求稳定。内置排序函数里Python 的 sorted 和 Java 对对象数组的排序底层都采用了归并排序的改进版本正是看中它的稳定性。外部排序则是归并排序真正不可替代的场景。假设机器内存是 2GB要排序的数据是 40GB所有数据根本塞不进内存快排、堆排这种“必须在内存里完成比较”的算法直接失效。归于并排序的做法是把 40GB 数据切分到内存能装下的多个小块每块在内存里排序后写回磁盘然后从每个有序块的开头读一部分数据进内存做一个多路归并不断输出最小的元素。因为归并的访问模式是顺序的——一个有序块被读完了才去读下一个块——对磁盘 IO 特别友好。机械硬盘最怕随机寻道顺序读写的速度比随机读写快一个数量级。这也是为什么数据库外排序、MapReduce 框架里的 shuffle 排序底层都在用多路归并。4.2 小数组阈值与改进版归并思路纯归并排序有一个实际短板当数组被递归拆分到很小的时候每次 merge 都要维护临时数组、做区间复制这些常数的开销相对偏高。而插入排序在小数组上非常快因为它的局部性很好、常数极小。工程实践里常见的优化是设置一个阈值比如当数组长度小于 16 或 32 时不再继续递归而是改用插入排序把小区间排好再回到归并流程。这就是一种混合排序策略。Python 和 Java 内置排序采用的改进版归并算法还运用了一个更聪明的观察真实数据往往天然存在一些已经有序的子段算法先扫描一遍把这些有序段识别出来对太短的段用插入排序扩展长度最后再用归并把各段合并。这种利用数据局部有序性的策略让实际排序速度常常接近线性。我在自己项目里做过一次简单改造把阈值设为 16其他逻辑不变对 100 万元素的随机数组排序时间大约减少了 20%。这个数字在不同语言、不同机器上会有差异但优化方向是确定的。4.3 链表排序省掉额外数组空间归并排序另一个被低估的优势是它可以很方便地用在链表上而且不需要额外的 O(n) 空间。数组归并需要临时数组是因为要从两个区间复制元素但链表排序只需要改指针。链表归并的思路用快慢指针找到链表中点把链表切成两半递归排好然后合并两个有序链表。合并时只调整节点的 next 指针不需要申请新节点。下面是一个完整的实现class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def sort_list(head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next mid slow.next slow.next None left sort_list(head) right sort_list(mid) return merge_two_lists(left, right) def merge_two_lists(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next这段代码对链表排序很实用。注意找中点时 fast 的初始值是 head.next不是 head这样做的目的是让慢指针停在左半部分的最后一个节点方便断链。这个细节我曾经写错过导致链表分成两半时左右不均出现了死循环。4.4 归并、快排、堆排怎么选做技术选型的时候我一般按下面这个思路快速判断。算法平均时间复杂度最坏时间复杂度额外空间稳定性主要适用场景归并排序O(n log n)O(n log n)O(n)稳定外部排序、链表排序、要求稳定的场景快速排序O(n log n)O(n²)O(log n)不稳定内存充足、通用排序、极致性能调优堆排序O(n log n)O(n log n)O(1)不稳定内存资源紧张、只需要 TopK 的场景插入排序O(n²)O(n²)O(1)稳定小数组、近乎有序的数组快排的优势是常数小、缓存友好在纯内存环境下通常比归并更快但它的最坏情况是 O(n²)并且不稳定。堆排序空间最优但常数很大实际速度往往不如快排和归并。归并排序没有明显的弱点代价就是那份 O(n) 的额外空间。我自己的经验法则如果排序的是自定义对象且业务上后续可能依赖原始顺序直接选归并或内置的稳定排序如果在内存里排基本数据类型、追求极致速度快排改好的实现更合适如果数据大到内存装不下别犹豫用多路归并做外部排序。5. 验证、调试与性能实测的心得5.1 排序算法最容易被“假通过”骗到排序算法看着简单但正确性验证其实比看起来麻烦。很多人跑一两个小用例看到结果有序就说“通过了”这不可靠。我习惯用一套固定的验证流程。第一步随机测试。生成规模不同的随机数组从小到大测比如长度 0、1、2、3、7、8、31、32、100、1000、10000每个长度跑几百次对比 Python 内置sorted()的结果任何不一致都要定位。第二步构造特殊输入。全逆序数组、全部相同元素、只含两个不同值的数组、完全有序数组、长度接近 2 的幂的数组、长度比 2 的幂大 1 的数组。这些用例分别覆盖了递归树不平衡、相等元素稳定性、边界切分等不同场景。第三步检查稳定性。给每个元素附带一个序号排序后检查相同值的元素序号是否依然升序。这一步特别适合验证你的 merge 里到底用的是还是。在用的实现中相等元素会取左侧的稳定性没问题如果用成相等元素会优先取右侧稳定性就悄悄被破坏了普通排序结果看起来还是对的但相对顺序已经变了。5.2 肉眼 debug 技巧与常见错误现象递归代码不好打断点因为调用栈一层套一层看起来头晕。我的办法是打印“进入区间”和“合并完成区间”两个日志像这样merge [0, 4) with [4, 8) - sorted [0, 8)把递归过程可视化之后很多问题就能直接看出来。比如如果日志里出现了某个区间越过了数组边界那多半是 mid 或 right 的 min 夹取没写对如果发现某个区间合并完结果还是无序的问题基本在 merge 里写回 arr 时下标错位或者是左右边界计算偏差。常见的错误现象有三类结果前一段有序后一段乱序通常是递归终止条件写错某段根本没有被合并整个数组基本有序但有个别元素错位往往是 merge 里剩余元素漏拷偶现死循环通常是链表切分没断开接点或者迭代版的 width 一直跳不出循环。5.3 一个直观的性能对比实测最后分享一次性能实测的经验。我用随机生成的一百万个整数在同一个环境里对比了三个手写算法和内置排序结果是内置排序最快其次是优化过的原地快排然后是归并排序最后是堆排。差距最明显的是堆排因为它的内存访问模式不够连续缓存命中率太低。归并排序和快排的差距其实没有想象中大在十万级数据下几乎感知不到差别。真正让归并排序在不少场景下胜出的不是常数而是稳定性。我在实际项目中重组过一个统计模块原来用快排结果两次运行产出不同的展示顺序排查到最后发现是排序不稳定导致的切换到归并后同样的输入永远产生同样的顺序这个问题直接从源头消失。这种“排序结果看起来没错但行为不可预测”的问题往往比明显的 bug 更难排查。所以我现在写业务代码时凡是会直接影响用户可见顺序的排序一律优先选择稳定排序。你的算法功底体现在能不能预判到这些小坑归并排序很多时候就是那把最稳的钥匙。最后说一个实操层面的个人习惯学任何排序算法我第一件事不是背代码而是拿一副扑克牌或者纸片自己手动做一次完整的归并过程。把数组拆到只剩单张牌再一张张合并回去走完一遍之后那些边界问题和终止条件就都不是死记硬背的知识了而是“我亲手做过的事”。这个习惯帮我省掉了大量阅读源码注释的时间也让我写递归函数时对“终止条件应该是什么”更有直觉。如果你正在被归并排序的递归绕得头晕不妨先放下代码试试纸笔模拟往往一下就通了。