归并排序从原理到实战：分治思想、复杂度分析与应用场景

1. 归并排序的精髓：先把问题拆到不能再拆，再有序地合回去

很多人第一次接触归并排序时，总觉得它不像快排、选择排序那样“直观”——快排的思想是“选个基准，小的左边、大的右边”，一听就懂；而归并排序上来就是“分、治、合”，听完概念以后自己写代码还是容易卡住。我自己当年学的时候也一样，看了两三遍原理图，觉得“哦，就是把数组切成两半，排好序再合并”，可真到动手的时候，递归边界怎么写？临时数组怎么开？合并的循环条件怎么判断？一下就乱了。

所以这篇文章我想换个角度来拆解归并排序：不只是讲它是怎么工作的，更重要的是讲清楚“为什么它是这样设计的”、以及“写代码时每一步在做什么”，这样你才能真正把它变成自己的东西，而不是背模板。

1.1 一个被低估的基础操作：“合并两个有序数组”

归并排序这个名字里的“归并”（Merge），指的是把两个已经有序的数组合并成一个更大的有序数组。这个操作本身特别简单，但它是整个归并排序的地基。

举个具体例子：有两个已经排好序的数组 A = [3, 8, 9]，B = [2, 5, 7]。要把它们合并成 C，常规做法是三个指针：

• 指针 i 指向 A 的开头，指针 j 指向 B 的开头；
• 每次比较 A[i] 和 B[j]，谁小就把谁放进 C，然后对应指针往后移；
• 直到其中一边先走完，再把另一边剩下的所有元素直接追加到 C 的末尾。

手动跑一遍就是：

• A[0]=3，B[0]=2，2 更小，C = [2]，j 移到 5；
• A[0]=3，B[1]=5，3 更小，C = [2, 3]，i 移到 8；
• A[1]=8，B[1]=5，5 更小，C = [2, 3, 5]，j 移到 7；
• A[1]=8，B[2]=7，7 更小，C = [2, 3, 5, 7]，j 越界；
• B 走完了，把 A 剩下的 [8, 9] 接上，C = [2, 3, 5, 7, 8, 9]。

这个操作的关键点是：对于两个长度分别为 n 和 m 的有序数组，合并的时间复杂度是 O(n + m)，因为每个元素最多被比较和搬动一次。这个“线性代价”看着不起眼，但它决定了归并排序整体效率的上限——正因为合并是线性的，归并排序才能做到 O(n log n)。

这里有个初学者容易忽略的细节：合并的前提是“两个子数组已经各自有序”。但人不会从天上掉下来两个有序数组，那怎么办？答案是通过递归拆分，把问题拆到“显然有序”为止。

1.2 分治到底“分”到了哪一步才算完

归并排序的分治逻辑是这样的：对于一个长度为 n 的数组，不断从中间切成两半，直到每一半只剩一个元素。一个元素天然就是有序的，根本不需要排序。

假设有数组 [6, 3, 7, 1, 9, 2, 8, 5]，完整的拆分过程是：

第一层：拆成 [6, 3, 7, 1] 和 [9, 2, 8, 5]；

第二层：[6, 3, 7, 1] 再拆成 [6, 3] 和 [7, 1]；[9, 2, 8, 5] 拆成 [9, 2] 和 [8, 5]；

第三层：[6, 3] 拆成 [6] 和 [3]；[7, 1] 拆成 [7] 和 [1]；[9, 2] 拆成 [9] 和 [2]；[8, 5] 拆成 [8] 和 [5]。

到这里，每个子数组都只剩一个元素，递归就到了底。接下来开始“治”的部分：把两个长度为 1 的数组按大小合并成有序的长度为 2 的数组，再把长度为 2 的数组合并成长度为 4 的数组，一层层往上，最后得到整个有序数组。

这个过程如果画成树，就是一棵完全二叉树，树的高度是 log₂n。这也是归并排序“必然 O(n log n)”的根本原因：不管初始数据是正序、倒序、还是完全随机，它拆分和合并的路径都是一样的，不存在快排那样“每次选的基准恰好都是最值导致退化到 O(n²)”的情况。换句话说，归并排序的时间复杂度是最坏情况下也稳定在 O(n log n)，这是它最重要的性格特征。

1.3 时间复杂度和空间复杂度到底怎么算出来的

先看时间。把递归过程看成树，每一层上所有子问题加起来的规模总和是 n。比如第一层处理整个数组，是 n；第二层两个子数组，加起来也是 n；第三层四个子数组，加起来还是 n。每一层合并的总代价都是 O(n)，而层数等于树的高度 log₂n，所以总的时间复杂度是 O(n log n)。

这个推导思路对理解分治算法很重要。很多教材直接丢一个递推公式 T(n) = 2T(n/2) + O(n)，然后用主定理求出 T(n) = O(n log n)。公式本身没错，但对初学者来说，不如“每层总代价是 n，共 log n 层”这个视角直观。

再说空间。归并排序需要的额外空间是 O(n)，这是它的一个明显短板。这里的空间主要来自合并时使用的临时数组——合并两个有序子数组时，不能直接在原数组上原地重排（至少常规写法不行），得先拷贝到一个临时数组里，比较完再拷回去。另外递归还需要 O(log n) 的栈空间，但 O(log n) 相对于 O(n) 可以忽略，所以归并排序的空间复杂度通常就说 O(n)。

这就引出一个很多人关心的问题：能不能把归并排序改成原地版本，把空间复杂度降到 O(1)？理论上可以，比如用旋转交换的方式原地合并，但代价是时间复杂度上升，而且实现极其复杂。我在实际项目中从没见过有人用原地归并排序，因为 O(n) 的额外空间在现代计算机上通常不是瓶颈，为了省空间把算法搞慢反而得不偿失。这点后面我会详细聊。

2. 手写归并排序：C++、Java、Python 三种实现对照

讲清楚原理之后，最有价值的部分就是把代码写出来。我见过不少学习者的纠结：原理看得明明白白，一到实现就卡壳。这里我给你三个语言的完整实现，对照着看，你就能发现归并排序的核心逻辑其实完全一样，差异只在语法层面。

2.1 C++ 实现：教科书式的递归写法

C++ 版本最适合理解归并排序的整个流程，因为可以用传引用直接操作原数组，每一步都看得很清楚：

void merge(vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; vector<int> L(n1), R(n2); for (int i = 0; i < n1; ++i) L[i] = arr[left + i]; for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } void mergeSort(vector<int>& arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); }

两点提醒：

• 计算中间位置时，用left + (right - left) / 2，不要用(left + right) / 2。虽然一般情况下两者结果一样，但 left + right 在极端场景下可能溢出，这是面试和工程中的经典细节。
• 合并时判断条件是L[i] <= R[j]，不是<。这个细节决定了排序是否“稳定”——等于号保证了相同元素的相对顺序不被打乱。后面我会专门说稳定性为什么重要。

2.2 Java 实现：和 C++ 几乎同构

Java 版本在思路上和 C++ 没什么区别，只是用数组和方法的组织方式不同：

public class MergeSort { public void mergeSort(int[] arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } private void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; System.arraycopy(temp, 0, arr, left, temp.length); } }

Java 版本里每次 merge 都新建一个长度等于当前子数组长度的临时数组，这是最清晰的写法，但频繁创建数组会有一定的性能开销。更讲究的做法是在外层一次性申请一个和原数组等长的临时数组，然后通过参数层层传入，避免反复分配内存。这个优化在数据量大的时候效果明显，我在实际项目里跑过百万量级的数据，性能差距可以达到两倍左右。

2.3 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 result.extend(left[i:]) result.extend(right[j:]) return result

这种写法最容易理解，但它有一个隐藏的性能问题：arr[:mid]和arr[mid:]每次递归都要拷贝子列表，而且merge里每层还要创建新的result列表，所以整体空间开销远大于 O(n)，在数据量较大时会有明显的内存压力。

如果想在 Python 里更节省空间，可以写成用索引切片配合辅助数组的版本：

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) 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: 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]

这个版本先在外面创建好一个temp数组，递归过程中反复复用它。实测下来，面对 10 万元素时，这个版本比切片版快三倍以上，内存占用也小得多。如果你在 Python 里经常处理排序任务，建议直接用这个写法。

3. 递归以外的选择：迭代式归并排序、原地归并的认知与优化空间

递归版的归并排序是教学重点，但在工程里，递归并不是唯一的选择，有时候甚至不是最好的选择。这一节我会讲两个有意思的方向：一个是自底向上的迭代式归并，另一个是围绕递归式的“优化迷思”。

3.1 自底向上的归并：不用递归，直接用循环控制合并区间

递归版的归并是“先拆到最底层，再逐层合并”，也就是自顶向下。但归并排序还有一个更符合“合并”本质的变体：自底向上。

思路是：把数组先看成 n 个长度为 1 的有序子数组，然后每两个相邻的子数组合并，得到长度为 2 的有序子数组；再两两合并，得到长度为 4 的；如此反复，直到整个数组有序。

void mergeSortIterative(vector<int>& arr) { int n = arr.size(); for (int width = 1; width < n; width *= 2) { for (int left = 0; left < n; left += 2 * width) { int mid = min(left + width - 1, n - 1); int right = min(left + 2 * width - 1, n - 1); if (mid < right) { merge(arr, left, mid, right); } } } }

这里的width可以理解为子数组的长度，外层循环每执行一轮，有序子数组的长度就翻一倍。mid是左半部分的右边界，right是右半部分的右边界，用min处理数组长度不是 2 的幂时末尾的越界问题。

自底向上的好处是不需要递归，自然就没有递归栈的 O(log n) 空间开销。对一些递归深度敏感的场景（比如嵌入式系统，或者递归深度受限的运行时环境），这个版本更合适。不过在日常应用里，递归版和迭代版的性能差距并不大，选哪个更多是看代码风格和具体场景。

3.2 终止递归条件与小区间插入排序的混合策略

递归版的终止条件是left >= right，也就是区间为空或只剩一个元素时直接返回。这个写法很干净，但还有一个常见的工程优化：当子区间长度小于某个阈值时，改用插入排序。

为什么？因为归并排序的递归调用是有固定开销的。当数组被拆得很小的时候（比如只剩 8 个、16 个元素），递归调用的开销占的比例会变得很大，此时直接用插入排序处理小数组反而更快。这不是玄学，而是真实存在的性能优化手段。像 JDK 里的Arrays.sort处理对象数组时，用的就是“归并排序 + 小数组插入排序”的混合策略：当数组长度小于某个阈值时，直接插入排序，避免无谓的递归开销。

我自己实测的经验：阈值取 7~16 之间比较合适，太小优化不明显，太大又会让插入排序本身的高频比较拖慢速度。这个优化在纯算法题里通常用不上，但在处理大规模真实数据的工程场景里，能省下不少时间。

3.3 “原地归并”为什么听起来很美，实战中却没人用

关于归并排序，网上一直有一个话题：有没有 O(1) 额外空间的归并排序？答案是“有，但没必要”。所谓原地归并，通常指的是用“旋转交换”或“块交换”的方式，把两个相邻有序段合并到一起，在移动过程中巧妙地利用数组本身的空间，从而避免临时数组。这种算法确实存在，而且时间复杂度仍然是 O(n log n)。

但问题在于：

• 实现极其复杂，边界条件多到让人头皮发麻，稍不留神就出 bug；
• 常数因子特别大，实际运行时间比普通归并排序慢很多倍；
• O(n) 的临时空间在现代计算机上几乎不是瓶颈。

我见过有人为了“炫技”在项目里写了原地归并，结果一上大数据就慢得让人怀疑人生。我的建议非常明确：如果你的排序场景需要原地操作、并且对空间极度敏感，那应该直接选堆排序或者快排，而不是跟归并排序死磕。归并排序的长处本来就不是空间，不要拿它的短板去比别人的长板。

4. 归并排序在实战中的落脚点：稳定性、外部排序和其他排序算法的对比

聊完代码实现和优化策略，接下来是更贴近真实应用的问题：归并排序在什么场景下是“最优解”？为什么很多标准库的排序算法都以它为基础？以及它和快排、堆排到底怎么选？

4.1 稳定性为什么在真实业务里如此关键

“稳定排序”的定义是：如果两个元素的排序关键字相同，排序后它们的相对顺序保持不变。

这个性质在纯数值排序里看不出什么价值，但在多维排序的场景里极其重要。举一个我实际遇到过的例子：某个电商后台需要对订单数据做展示，希望同一天内的订单按下单时间从早到晚排序。最简单的做法是先按日期排序，再按时间排序。但如果第二次排序用的是不稳定排序，第一次按日期排好的结果就可能被打乱——同一个日期内的订单依然按时间有序的前提是“第二次排序是稳定的”。这就是为什么很多对象排序场景必须首选稳定排序算法。

归并排序恰好是稳定的。因为它在合并两个有序子数组时，采取的是“左边元素 <= 右边元素时，先取左边”，这保证了相同关键字的元素来自左半部分时，会排在来自右半部分的同关键字元素前面。随着递归一层层合并，这个稳定性会被完整地传递到最终结果中。

Java 的Arrays.sort对对象数组使用 TimSort（一种以归并排序为基础的增强版稳定排序），正是因为业务上经常需要给对象做多字段排序；而对基本类型数组使用双轴快排，则是因为基本类型不存在“相对顺序有意义”的问题。这个设计本身就是对“稳定性的业务价值”的最好说明。

4.2 外部排序：归并排序的主场，没有之一

如果说稳定性是归并排序在通用领域的优势，那外部排序中大放异彩则是它的杀手级应用。

什么叫外部排序？当数据量大到无法全部加载进内存时（比如内存只有 8GB，但数据有 100GB），无法直接调用内存排序算法完成排序，这时候只能把数据一部分一部分地读进内存、排序、写回磁盘，并通过多次归并来得到最终有序的结果。这个场景里，归并排序几乎是唯一现实可行的选择。

典型的外部排序流程是：

1. 把大文件切分成多个可以完全装入内存的小块，每块在内存里排序后写回磁盘，得到多个有序的子文件（称为“归并段”或“run”）；
2. 通过多路归并（k-way merge）的办法，同时打开 k 个归并段，每次从 k 个文件中挑出最小的元素写入输出文件，不断重复，直到所有归并段都被消费完；
3. 如果归并段数量仍然很多，还可以采用多轮归并、败者树、置换选择等优化手段来减少磁盘读写次数。

这个过程里，第一步在内存中排序小块数据用的算法通常也是快排，但第二步的多路归并，本质上就是归并排序“合并两个有序数组”思路的放大版。可以说，归并排序是外部排序的基石。你搜索“mysql排序”“excel 排序”这类话题时，如果数据量大到内存装不下，底层机制几乎都能看到归并的影子。

4.3 归并排序 vs 快排 vs 堆排：一张表看懂怎么选

很多人在学完这些主流排序算法后会纠结一个问题：日常写代码到底该用哪个？其实在工程里，你通常不需要自己写排序算法，直接用语言内置的sort就够了。但了解底层差异，能帮你理解为什么标准库做了那样的选择，也能在你面对特殊需求的时候做出正确决策。

我用下面的表格把归并排序、快排、堆排的核心区别整理清楚：

由此可见，归并排序不是在所有场景下都最优，但它的“稳定 + 最坏情况也有保证 + 天然支持外部排序”这几个特性，让它成为一个不可替代的存在。很多标准库没有直接采用纯归并排序作为通用排序方案，主要是因为它需要 O(n) 的额外空间，但会像 TimSort 那样以归并为基础设计出更贴近实际数据分布的增强算法。

5. 写归并排序最容易翻车的细节：边界条件、递归栈和常见误区

最后这部分，我把自己这些年写归并排序踩过的坑、以及给学员讲课时反复强调的细节集中整理一下。排序算法看起来简单，但真到关键时刻，往往是这些不起眼的细节决定你写得对不对、快不快。

5.1 边界条件：一个符号错误，结果全乱

归并排序里最经典的边界问题在两个地方：递归终止条件和合并循环的结束条件。

递归终止写left >= right而不是left == right，是为了防止非法区间。比如调用mergeSort(arr, 5, 4)这种不可能出现的场景时，直接返回，避免无限递归。虽然正常流程不会出现left > right，但写上>=是一种防御性编程的习惯。

合并循环里最容易错的则是i <= mid和j <= right。很多人受数组下标从 0 开始的影响，容易写成i < mid或者j < right，这样会导致最后一个元素被漏掉。这个 bug 极其隐蔽，因为结果看起来只是顺序不太对，很难一眼看出问题。我的经验是：把合并的两个子数组想成“闭区间 [left, mid]”和“[mid+1, right]”，每次循环边界都按照闭区间的思路写，就很少出错。

5.2 不要盲目追求“优雅”而忽略可读性

网上有很多“一行流”的归并排序实现。比如 Python 里有人写这种：

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

看起来很简洁，但可读性并不好，而且性能也一般。我建议初学者还是老老实实把递归 + 合并拆成两个函数来写。一方面逻辑更清晰，另一方面测试的时候可以单独测试merge函数——把两个有序数组合并的逻辑单独验证通过后，再去测mergeSort，排查问题会快很多。我自己在实际工作里调排序相关代码时，也一直用这个策略：先保证子函数是对的，再上整体。

5.3 递归深度与栈溢出的隐患

归并排序的递归深度是 log₂n，所以正常情况下几乎不会栈溢出。但如果你在一个递归深度极敏感的运行时里写归并排序（比如某些嵌入式环境或者自定义的虚拟机上），100 万元素也就 20 层递归，一般没问题；可如果数组长度到千万级，递归深度也只有 24 层左右。真正的风险往往来自你无意中把递归写成了类似于“每次都只排好一部分，剩下的没递归完”的不平衡递归，那样的话递归深度会被拉到 n，直接爆栈。

如果你实在不放心，可以用前面提到的迭代式归并，彻底避开递归深度问题。

5.4 变体应用：链表排序、字符串排序、结构体排序

归并排序的思想不仅能处理数组排序，在处理链表排序时同样很好用。链表的归并排序不需要额外开辟数组空间，因为节点本身可以通过指针“重新连接”，所以只需要递归地找到链表中点，拆成两半，分别排序后再合并。很多大公司的面试题都会考链表排序，而标准答案几乎都是归并排序——因为快排对链表的随机访问支持不好，堆排序又需要数组才能做堆化。所以如果你最近在准备面试，链表归并排序值得专门练一练。

另外，“字符串排序”和“结构体排序”这两个搜索热词，正好也是归并排序的用武之地。字符串本质上可以按字典序比较大小，结构体可以选择任意一个或多个字段作为排序关键字——只要比较函数写得对，归并排序的特性（稳定 + 最坏 O(n log n)）能让它们都受益。

5.5 把归并排序当工具用，还能解决“逆序对”问题

别以为归并排序只会排序，它还有一个很经典的“副产品”：求数组中逆序对的数量。

逆序对的定义是：对数组中的两个下标 i < j，如果 arr[i] > arr[j]，就称这两个元素构成一个逆序对。最粗暴的解法是双重循环，时间复杂度 O(n²)。但借用归并排序的流程，可以在合并两个有序子数组时顺便统计：当右边子数组中的元素 arr[j] 小于左边子数组中的元素 arr[i] 时，说明左边子数组中 i 到 mid 之间的所有元素都比 arr[j] 大，这些都可以和 arr[j] 构成逆序对，所以逆序对数量要加上mid - i + 1。

这个技巧在“计算一个数组的有序程度”“相似度比较”等场景里非常实用。你在搜索“归并排序原理 java”“排序法时间复杂度怎么算”这些热词时，大概率也会翻到这个结论——它说明归并排序的价值远不止排序本身，而是分治思想的一种绝佳载体。

就我自己多年的实践体会来说，如果你能把归并排序真正吃透，你对“分治”这两个字的理解会比看十道算法题都深。写的时候我建议你先把merge函数单独写好、测好，再套上递归外壳，这样能省去大量排查时间。等你熟练了，再试着去实现链表版本、逆序对统计和迭代式写法，你对排序的理解就会越来越立体。