分治法与归并排序：从递归思想到工程实践

很多人在学算法的时候，排序算法背了一堆，冒泡、选择、插入张口就来，但一提到“分治法”三个字，脑子里就只剩一个模糊的概念：好像是把大问题拆小，然后呢？归并排序（Merge Sort，也叫合并排序）就是分治法最经典、最干净的一个载体——代码不长，逻辑清晰，但背后包含的“分解-解决-合并”思想，足够你迁移到一大类算法问题上。这篇文章我想从一个实际写代码的人的角度，把这套东西彻底拆开讲透：分治法到底在干什么，归并排序每一行代码为什么这么写，复杂度是怎么算的，以及我踩过的那些坑。

如果你正准备啃算法教材、刷题练递归，或者面试前想把手写排序练到条件反射的程度，这篇文章就是按这个目标来的。我会从思想讲到实现，再讲到变种应用，最后放一些实战中会碰到的边界问题和排查方法。

1. 分治法不是一种具体算法，而是一种思维方式

1.1 分治的三步套路

分治法（Divide and Conquer）不是一个算法，它是一种解决问题的节奏。官方说法是三步：分解、解决、合并。翻译成人话就是：把一个大任务拆成几个独立的小任务，小任务解决了，再把结果拼起来。

举个例子，假设你手里有全年级 800 人的成绩单，要按总分从高到低排好。一个人排 800 条记录不算难，但很慢。分治的做法是：把成绩单分成两半，每 400 人一组；如果 400 人还是多，就继续分，分到每组只剩一两个人为止；每个人自己排序当然毫无压力；最后把两个已经排好序的小组合并成一个有序的大组。这个过程不断重复，最终 800 人的成绩单就整体有序了。

关键点在于：合并两个有序序列，比直接排序一个无序序列要快得多。就像你手里有两副分别排好序的扑克牌，你只需要不断比较最上面一张，挑小的放一边，就能快速得到一副完整的排序牌。如果没有“分别排好序”这个前提，合并这一步就无从优化，只能老老实实做全局比较。

1.2 为什么“拆开做”反而更快

一个常见疑问是：把排序拆成两个子排序，每个子排序还是没少比啊，凭什么更快？答案藏在合并这一步。

想象直接排序 8 个数字（比如插入排序），一个数字要和前面所有数字比较才能找到位置，最坏情况比较次数接近 O(n²)，也就是 8 个数字最坏约 28 次比较。而归并排序的思路是：先把 8 个拆成 1+1+1+...，然后两两合并。合并时你永远不会做无效的跨区间比较，因为你总是知道两个子数组内部已经有序，每次只需要比较两个子数组的当前最小值。这样每一层合并的代价只有 O(n)，层数是 log₂n，总代价 O(n log n)。

从直觉上理解：直接排序里，一个元素要逐个跟前面的元素比，比完一次只能前进一个位置。分治之后，元素通过各层合并，能利用“局部有序”跳过大量无效比较。这也是为什么 n 越大，归并排序相比 O(n²) 排序的领先越明显——数据规模从 1000 涨到 10000，插入排序的时间大约涨 100 倍，而归并只涨 13 倍左右。

1.3 什么样的场景才适合分治

不是所有问题都适合分治。一个合格的分治场景，一般需要满足三个条件：

• 可以把问题分解成若干个规模更小的子问题
• 子问题之间相互独立，互不影响
• 子问题的解能高效合并成原问题的解

反过来，如果子问题之间存在大量重叠，比如计算斐波那契数列时递归分解成 f(n-1) 和 f(n-2)，它们会重复计算大量相同的子问题，这种场景直接分治会导致指数爆炸，更适合用动态规划或者备忘录。所以学归并排序时不光要会写，还要能判断“分治这个思路用在这里是不是合适”，这才是算法素养。

2. 归并排序的核心拆解：递归过程与 merge 函数

2.1 递归的“递”和“归”

归并排序的递归实现，看起来就两段逻辑：先递归排序左半，再递归排序右半，然后合并。但真正理解递归，要分清楚“递”和“归”两个阶段。

拿数组 [8, 3, 5, 1, 7, 2, 6, 4] 举例。“递”的过程是把数组不断二等分，直到每组只有一个元素：8 | 3 | 5 | 1 | 7 | 2 | 6 | 4。当递归走到长度为 1 的数组时，不再继续，这时候开始“归”——两个长度为 1 的数组归并成长度为 2 的有序数组，比如 [3, 8]；两个长度为 2 的数组归并成长度为 4 的有序数组；最后两个长度为 4 的数组归并成完整的有序数组。

理解这个过程的诀窍是：不要试图追踪整个递归栈，你只需要相信两件事：第一，左半子数组调用归并排序后返回的是有序的；第二，右半子数组调用归并排序后返回的也是有序的。只要 merge 函数能把两个有序数组合并成整体有序，整个排序就是正确的。这就是递归里的“归纳假设”。

2.2 merge 函数：一切的关键

归并排序里的灵魂不是递归，而是 merge。递归只是把问题切到足够小，真正干活的是合并两个有序数组。

合并的逻辑可以用双指针描述：

1. 初始化两个指针 i、j，分别指向左子数组和右子数组的起始位置
2. 比较 left[i] 和 right[j]，把较小的放进结果数组，对应指针往后移
3. 重复直到一边走完
4. 把剩下还没走完的子数组剩余部分全部追加到结果数组

为什么这个操作是 O(n)？因为每放一个元素，指针就推进一格，总共只有 n 个元素要被放入结果，所以最多 n 次比较和 n 次赋值，线性复杂度。

这里有一个细节：如果两个元素相等，应该先取左边的还是右边？答案是取左边。这能保证稳定性，这点后面细说。

2.3 稳定性为什么重要

稳定排序的意思是：两个值相等的元素，排序后相对顺序和排序前保持一致。归并排序在合并时，如果 left[i] 和 right[j] 相等，我们先把 left[i] 放入结果，这样左边数组的元素仍然排在右边数组里相等元素的前面，稳定性就保住了。

实际工程里稳定性价值很大。比如一个用户列表先按注册时间排好，再按城市分组。如果第二个排序不稳定，同一城市里用户的注册时间顺序就可能被打乱；用稳定排序，城市分组后城市内部仍然保持注册时间有序。数据库的排序、某些需要多关键字排序的场景，都会关注稳定性的要求。

上面它本身是稳定排序。只要在 merge 判断时使用<=而不是<，相等元素就可以稳定地从左半区先走，这是归并排序的天然优势。

2.4 哨兵值写法与边界判断的取舍

merge 函数有一种教科书写法，是在左右子数组末尾放一个“哨兵值”（通常是正无穷），这样循环里就不需要判断数组是否越界，只要碰到哨兵，肯定比另一边大，循环自然结束。

但我在实际使用中不太推荐这种写法。表面上是简化了代码，实际上有坑：如果数组里本来就存储了极大值（比如数据库里的最大值），哨兵可能产生混淆；如果数组是浮点数且包含 NaN，比较结果会变得异常；如果用来排序的是对象，还需要额外定义无穷大对象，非常别扭。更稳妥的做法是老老实实写索引越界判断，虽然代码长几行，但鲁棒性好，面试时也不容易翻车。

两种写法后面代码章节都会给出，你可以自己对比手感。

3. 手写一个完整的归并排序：从递归版本到迭代版本

3.1 Python 最清晰版本

我用 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): 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 # 剩余部分直接拼接 if i < len(left): result.extend(left[i:]) if j < len(right): result.extend(right[j:]) return result

这个版本有两个缺点：一是每次递归都切片，会额外创建大量列表；二是不支持原地修改原数组。教学没问题，但如果你要在生产环境或者刷题时追求性能，需要改成基于索引的写法。

3.2 基于索引的 Python 版本（推荐练习写法）

def merge_sort_inplace(arr): n = len(arr) temp = [0] * n # 一次性申请临时数组，避免反复创建 _merge_sort(arr, 0, n - 1, temp) return arr def _merge_sort(arr, left, right, temp): if left >= right: return mid = (left + right) // 2 _merge_sort(arr, left, mid, temp) _merge_sort(arr, mid + 1, right, temp) _merge(arr, left, mid, right, temp) def _merge(arr, left, mid, right, temp): i, j = left, mid + 1 k = left while i <= mid and j <= right: if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: temp[k] = arr[j] j += 1 k += 1 while i <= mid: temp[k] = arr[i] i += 1 k += 1 while j <= right: temp[k] = arr[j] j += 1 k += 1 # 把临时数组中排好的部分复制回原数组 for idx in range(left, right + 1): arr[idx] = temp[idx]

注意最后一个 for 循环——很多人会把整个 temp 数组复制回去，这是错的。只需要复制 [left, right] 这个区间，否则会把不相关的数据弄乱。我在最开始学的时候因为这里写错了，查了很久才定位到问题。

3.3 JavaScript 版本：面试最常用

如果你在准备前端或后端开发面试，手写 JavaScript 版是高频题：

function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); } function merge(left, right) { const result = []; let i = 0; let j = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.push(left[i++]); } else { result.push(right[j++]); } } // 剩余元素拼接（这里也可以利用 concat） while (i < left.length) result.push(left[i++]); while (j < right.length) result.push(right[j++]); return result; }

JavaScript 版本的性能瓶颈和 Python 切片版一样，都在于拆分数组时的 slice。刷题无所谓，但如果面试官追问优化方式，你需要能说出用索引指针避免反复切片的写法。

3.4 迭代版：不用递归也能归并

递归版本逻辑清晰，但如果你对递归不放心，或者想展示对算法的更深入理解，可以写自底向上的迭代版。核心思路是用宽度变量 width 控制合并区间大小：

def merge_sort_iter(arr): n = len(arr) temp = [0] * n width = 1 while width < n: for start in range(0, n, 2 * width): mid = min(start + width - 1, n - 1) end = min(start + 2 * width - 1, n - 1) if mid < end: _merge(arr, start, mid, end, temp) width *= 2 return arr

这段代码里，width 从 1 开始，代表当前合并的子数组长度。第一次合并长度为 1 的相邻元素，第二次合并长度为 2 的块，第三次合并长度为 4 的块，以此类推。需要注意的边界是数组长度不一定是 2 的整数次幂，所以 mid 和 end 都要用 min 限制在范围内。

迭代版的好处是不用担心递归深度，也直观地展示了归并排序的本质“两两合并有序块”。有些工程师偏好这种实现，因为可以完全避免函数调用开销。

提示：如果你写递归版会在某些语言里爆栈，不要慌。归并排序递归深度是 log₂n，比如 100 万个元素深度也只有 20 层左右，一般不会触发栈溢出。真正危险的是把递归写成每次只减少一个元素（比如错误的斐波那契），那才算灾难。

3.5 关于“原地归并排序”的说法

不少初学者听说过归并排序可以做到原地排序，于是试图把 merge 操作直接在原数组上交换完成。严格来说，纯数组的原地归并排序虽然空间复杂度能做到 O(1)，但时间复杂度可能退化到 O(n² log n)，工程上几乎没人用。

真正的例外是链表——链表归并排序可以通过调整节点指针实现空间 O(1) 的辅助空间，同时保持 O(n log n) 时间复杂度和稳定性，这是链表排序的最佳选择之一。这个场景下面第 6 章会展开聊。

4. 复杂度推导与排序选型：什么时候该用归并

4.1 递归式与时间复杂度推导

归并排序的时间复杂度可以用一个递归式表达：

T(n) = 2T(n/2) + O(n)

含义是：排序规模为 n 的数组 = 排序规模为 n/2 的两个子数组 + 合并两个子数组的线性开销。用递归树展开：

• 第 0 层：1 个问题，合并开销 O(n)
• 第 1 层：2 个问题，每个合并开销 O(n/2)，总开销 O(n)
• 第 2 层：4 个问题，每个合并开销 O(n/4)，总开销 O(n)

每一层加起来都是 O(n)，树的层数是 log₂n，所以总复杂度 O(n log n)。这个复杂度很稳定，无论数据原来是否有序，归并排序总是先拆到底再合并，不会像快排那样出现最坏 O(n²) 的情况。

如果你学过主定理，也能直接套用：a=2，b=2，f(n)=O(n)，f(n) 和 n^(log_b a)=n 同阶，属于 Case 2，结果 T(n)=O(n log n)。

4.2 空间复杂度：O(n) 花在哪了

归并排序不是原地排序，它的空间复杂度是 O(n)。主要两部分：

• 临时数组：合并时需要一块和原数组等长的空间来暂存结果
• 递归调用栈：深度为 log₂n，每层常数空间

你如果每次递归都创建新数组来承载 left 和 right，空间并不会变成 O(n log n)，因为递归是深度优先的，左半部分的数组在右半部分计算前就可以被回收。任意时刻栈上最多存在 O(n) 的切分数据，加上每层递归的临时数组，整体就是 O(n)。

但注意，Python 切片版使用的 arr[:mid] 会在每轮递归创建新列表，内存抖动比较厉害；生产代码应尽量复用临时数组，这也正是 3.2 节版本的意义。

4.3 与快排、堆排的对比

为了让你在选型时有清晰判断，经验总结如下：

可以看到，归并排序的优势是表现稳定且稳定排序；劣势是需要额外 O(n) 空间。快排平均性能很好，额外空间小，但最坏情况退化（虽然可以通过随机化 pivot 大幅度规避）；堆排序空间最优，但常数系数偏大且不稳定。

4.4 实际选型建议

• 内存充足、稳定性要求高：选归并排序
• 对数组进行常规排序且不要求稳定：快排通常是更优选择（工程实现普遍默认快排思想）
• 内存限制严格：考虑堆排或者原地快排
• 链表排序：用归并排序，可以做到 O(1) 辅助空间且稳定
• 数据量超大、内存放不下：外部排序，下面会专门讲

5. 实操经验与常见问题排查实录

5.1 递归边界写错：空数组直接爆栈

初学者最常见的错误是递归出口写成if len(arr) == 1: return arr，但忽略空数组。当输入是空数组或递归切分时产生空数组，函数会一直递归下去，直到栈溢出。

正确的检查标准是if len(arr) <= 1。这个 <= 看似不起眼，却能同时覆盖空数组和单元素数组两个边界。

5.2 合并循环写了 or 导致越界

常见的错误版本：

while i < len(left) or j < len(right): if left[i] <= right[j]: ...

一旦 i 走到了 left 的尾部，left[i]就越界了。正确写法是and，这样只要有一方走完就退出循环，剩下的元素直接拼接。顺序是先循环比较，再处理剩余，两个阶段必须分开。

5.3 Python 切片的性能陷阱

用切片写法非常直观，但在处理大数组时有明显性能问题：每次递归都复制出一半的数组，时间开销和内存开销都被放大了。我做过一个测试，1 万个随机整数排序，切片版比索引版慢一倍以上；到 10 万元素，切片版的内存占用非常夸张。刷题、小规模数据无所谓，但如果你在做数据处理或者研究排序性能，一定要用索引传递的方式。

同样的道理也适用于 JavaScript 的 slice 和 concat。表现力强的代码不等于高效的代码，这是工程里常见的取舍。

5.4 用归并排序统计逆序对：面试常见加分项

归并排序在合并时有一个隐藏能力：统计逆序对。如果左边数组的当前元素大于右边数组的当前元素，那么左边数组剩余的所有元素都比右边当前元素大，它们就构成了若干个逆序对。

在 merge 过程中加入一行计数即可：

count += mid - i + 1 # 或 len(left) - i，取决于你的变量命名

完整实现：

def count_inversions(arr): n = len(arr) temp = [0] * n result = [0] # 用列表包装计数器，方便在嵌套函数中修改 def merge_count(left, mid, right): i, j, k = left, mid + 1, left while i <= mid and j <= right: if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: # 左半部分从 i 到 mid 的所有元素都与 arr[j] 构成逆序对 result[0] += mid - i + 1 temp[k] = arr[j] j += 1 k += 1 while i <= mid: temp[k] = arr[i] i += 1 k += 1 while j <= right: temp[k] = arr[j] j += 1 k += 1 for idx in range(left, right + 1): arr[idx] = temp[idx] def sort_section(left, right): if left >= right: return mid = (left + right) // 2 sort_section(left, mid) sort_section(mid + 1, right) merge_count(left, mid, right) sort_section(0, n - 1) return result[0]

这个问题的应用题语境通常是“找出数组中逆序对的数量”，暴力解法 O(n²)，归并排序解法 O(n log n)。熟练了这个写法，面试时能省下大量思考时间。

5.5 我踩过的几个实际坑

第一个坑是哨兵值。我早期用float('inf')做哨兵处理纯数字列表，一切正常。后来在一个业务系统里排序的对象嵌入了各种数值类型，里面混了一个字符串，结果直接报 TypeError。自那以后我再不写哨兵，宁可循环里多判断几次越界。

第二个坑是临时数组复用。用索引版时，如果在递归函数内部新建临时数组，最终空间复杂度仍然是 O(n) 没错，但如果你在递归过程中错误地把临时数组作为全局共享，两个正在进行的合并操作会互相覆盖数据。这个问题比较隐蔽，表现出来是“某些区间排序正确，某些区间数据丢失”。排查方法是在 merge 函数的开头加断言，确认 temp 相关区间没有残留数据。

第三个坑是对已经接近有序的数据用归并排序不一定划算。工程内置排序往往会针对接近有序的数据做优化（比如检测已排序的连续片段直接合并），而经典归并排序一刀切地二分到底，遇到本来大部分有序的数据也不会更快。这个特性决定了它作为通用排序工具的一些局限。

5.6 写递归的几个小技巧

如果你对递归总是心里没底，调试归并排序有一个特别有效的方法：打印递归深度和区间。在_merge_sort开头加上深度参数，打印当前正在排序的区间[left, right]，你会直观看到递归如何把区间不断二分，最终有序地合并回来。用 3-4 个元素的数组跑一遍，比看十篇文章都管用。

6. 从归并排序延伸出去：变体、应用与学习建议

6.1 外部排序与多路归并

归并排序最实用的工业级应用之一，是外部排序。当数据量大到无法全部加载进内存（比如 100GB 的日志文件，内存只有 1GB），普通排序算法直接没法用。外部排序的思路是：

1. 把大文件切成多个能装进内存的块
2. 每个块单独读入内存，用快排或系统排序排好，写回磁盘
3. 对所有有序块做多路归并：每块维护一个指针，每次从所有块中挑最小的元素输出，不断推进

这就是归并思想的放大版。当路数很多时，线性扫描每块找最小值太慢，工程上会用一个大小为 k 的最小堆来优化“从 k 个块里选最小值”的过程，复杂度从 O(k) 降到 O(log k)。

这个场景完美诠释了“合并有序序列”这件事的价值。我不会说外部排序就是归并排序，但如果你能理解归并排序的 merge，外部排序的核心你已经掌握一半了。

6.2 链表上的归并排序

数组版归并排序需要 O(n) 辅助空间，因为在合并时需要临时空间来存放结果。但链表排序可以通过调整节点指针，实现真正意义上 O(1) 额外空间的归并排序，并且保持稳定。

做法也很直观：用快慢指针找到链表中点，递归排序左右两半，然后交叉比较两个链表的节点，把小节点链接到结果链表的尾部。由于只需要改变 next 指针，不需要额外的数据容器，空间复杂度降下来了。这也是为什么很多算法题目里“链表排序”首选归并排序而不是快排——快排需要双向访问或额外的指针操作，在单链表上很别扭；堆排则需要随机访问数组来维护堆，在链表上无法实现。

6.3 分治法的其他经典案例

归并排序只是分治法的入门。理解分治之后，你会在很多算法里看到相似套路：

• 最大子数组问题：拆成左右两半，最大子数组要么完全在左半，要么完全在右半，要么跨越中点，解决后合并取最大
• 最近点对问题：按 x 坐标拆分成两半，递归求左右最小距离，再检查跨中线的带状区域
• 大整数乘法：把大整数分成高位低位，减少乘法次数来降低复杂度

这些问题的共性都是：先想清楚子问题边界，再想清楚合并逻辑。归并排序合并的是“两个有序数组”；最大子数组合并的是“跨越中点的最大子数组”；最近点对合并的是“跨中线的最近点对”。合并步骤的巧妙程度，直接决定整个算法的质量。

6.4 学习算法的一点体会

回看这段学习经历，我觉得归并排序是最适合用来建立“递归信心”的例子。它代码不长，边界条件明确，画图容易，而且每一层递归都有非常具体的操作（合并）。当你亲手把递归版、迭代版、逆序对版都写一遍，再回头去看其他递归算法，会从容很多。

如果你正在被递归折磨，我的建议是：不要只看不练。拿起纸笔，手动模拟一个 4-5 个元素的数组，把递归调用栈一层层画出来，再对照代码走一遍。这个过程很笨，但效果极好；过了这道坎，你会发现分治法其实就那三板斧——拆到最小、递归解决、合并结果。

最后再分享一个我自己的小习惯：学任何一个新算法，我都会问自己三个问题。它能拆吗？子问题独立吗？合并代价大吗？三个问题都回答“是”，分治法大概率能用；如果有一个回答是否定，就换思路。这套判断框架，比记住某个具体算法要重要得多。