排序是每个写代码的人绕不过去的坎。面试要问、工程要用、算法竞赛也要考。很多人一上手就是冒泡、快排，真正把归并排序吃透的反而没几个。但我个人的体会是，归并排序这玩意看着简单，背后藏着的分治思想、稳定性设计和空间换时间的权衡，几乎贯穿了计算机科学里最核心的思维方式。你要是能把它彻底搞明白，后面看线段树、看CDQ分治、看外部排序，都会顺很多。

这篇文章我不打算整那些教科书式的定义，而是直接站在动手实现的角度去拆。先讲清楚它到底聪明在哪，然后给你能直接抄的模板，再拿一个具体数组完整推演一遍归并过程，最后把我实际调试中踩过的坑和排查思路全抖出来。内容尽量说人话，但该有的算法分析、复杂度推导一点都不会省。

1. 归并排序到底在解决什么问题：核心设计与思路拆解

1.1 从排序的“稳定”需求说起

先问一个问题：排序这件事，除了把数字从小到大排好之外，到底还有什么隐性的要求？

答案是稳定性。所谓稳定，指的是如果两个元素的值相同，排序之后它们的相对顺序不能变。这个性质在绝大多数场景下是被忽视的，但只要你的数据带“主键+副键”的多级排序需求，稳定性就是救命的。比如先按分数排，再按学号排；或者先按部门排，再按入职时间排。如果排序算法不稳定，第二趟排序会把第一趟的结果打乱，你只能被迫用“组合成一个新的比较键”这种笨办法去规避。

快速排序的经典实现（比如以最后一个元素为基准的Lomuto划分）是不稳定的，堆排序也不稳定。而归并排序，只要你在合并两个有序子数组的时候，遇到相等元素总是优先取左边子数组的元素，它就是稳定的。这一个细节，就是归并排序身上最核心的设计选择之一。理解了这一点，你就知道为什么在很多强调稳定性的底层库函数里，归并排序或它的变体总有一席之地。

1.2 分治：把大问题拆到不用排序为止

归并排序的思路其实特别朴素，就一句话：先把数组从中间劈成两半，把两半分别排好，再把两个有序的序列合并成一个有序的序列。这个“劈开”的动作不断递归下去，直到子数组里只剩下一个元素——一个元素天然有序，不需要再做任何处理。这整个流程，就是分治算法最标准的模板：分解、解决、合并。

这里面最漂亮的设计在于“合并”这一步。合并两个已经有序的数组，不需要任何比较排序的“回溯”过程，只需要两个指针从头往后扫，谁小就取谁，时间复杂度是线性的O(n)。正是因为“合并”是线性的，整个算法的递归式是T(n) = 2·T(n/2) + O(n)，解出来就是O(n log n)。

你可能会想，快排不也是分治吗，为什么快排最坏会退化到O(n²)，而归并排序不会？因为快排的“分”依赖基准元素的选择，运气差的时候每次只能把数组分成1和n-1两部分；而归并排序的“分”是纯靠下标平均切割的，无论数据长什么样，切割点总是确定的。这个“确定性”是归并排序时间复杂度永远稳定的根本原因。

1.3 经典之下隐藏的取舍：为什么它不是万能药

归并排序也不是没有代价。它最大的问题就是空间复杂度。你合并两个有序数组的时候，没法完全不借助额外空间就地完成（虽然也有原地归并的变体，但常数大得离谱，工程上基本没人用）。所以经典的归并排序需要一个和原数组等长的临时数组，空间复杂度是O(n)。

这听起来好像没什么，但在嵌入式环境、内存极其受限的场合，这可能是致命的。另外，对于纯数字排序这种缓存友好的场景，归并排序的“跨数组访问”模式比快排的“局部扫描”模式要吃亏，实际运行速度往往不如优化良好的快速排序。

所以工程上经常干的事情是“杂交”：数据量小的时候用插入排序，数据量大的时候用归并排序，中间还可以插进快排。后面我会细讲这些优化思路，都是能直接用到实际项目里的。

2. 从伪代码到能跑的代码：核心细节解析与实操要点

2.1 先写一版教科书级的递归实现

这里我用Java来写，因为Java的数组操作直观，而且读代码的人基数大。Python、C++的写法逻辑完全相同，只是语法差异。

public class MergeSort { public static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 一次性申请临时数组，避免递归过程中反复创建对象 int[] temp = new int[arr.length]; sort(arr, 0, arr.length - 1, temp); } private static void sort(int[] arr, int left, int right, int[] temp) { // 递归终止条件：区间内只剩下一个元素或空区间 if (left >= right) { return; } int mid = left + ((right - left) >> 1); // 防止 left + right 溢出 sort(arr, left, mid, temp); sort(arr, mid + 1, right, temp); merge(arr, left, mid, right, temp); } private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 左半区起点 int j = mid + 1; // 右半区起点 int t = 0; // 临时数组游标 // 两个子数组都有剩余元素时，谁小取谁 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { // 注意这里是 <=，保证稳定性 temp[t++] = arr[i++]; } else { temp[t++] = arr[j++]; } } // 左半区有剩余 while (i <= mid) { temp[t++] = arr[i++]; } // 右半区有剩余 while (j <= right) { temp[t++] = arr[j++]; } // 把临时数组的结果拷回原数组的对应区间 t = 0; while (left <= right) { arr[left++] = temp[t++]; } } }

这段代码看起来平平无奇，但里面有几个细节是很多教程不会告诉你的。

第一个细节是mid的计算采用left + ((right - left) >> 1)而不是(left + right) / 2。原因很简单，如果left和right都接近int上限，left + right会溢出变成负数，导致mid计算错误，程序直接崩溃。虽然一般业务数据让数组长度塞满int不现实，但这是一个良好的编码习惯。

第二个细节是临时数组只申请一次，而不要在每个递归层级的merge方法里new一个。如果每次merge都new int[arr.length]，递归深度logn，每次合并都分配大块内存，性能会惨不忍睹。一次性申请、随递归传下去，是归并排序工程化时最基本的内存优化。

第三个细节是merge里的第一个while循环，判断条件是<=而不是<。这个小于等于号就是稳定性的灵魂。当左右两个元素相等时，我们取左边的元素放入临时数组，这样相等元素的相对顺序就能保持原样。如果你写成<，那相等时右半区的元素会先被取出，稳定性直接破功。

2.2 自底向上的迭代实现：摆脱递归栈恐惧

很多人一看到递归就头大，担心递归深度太深导致栈溢出。实际上，因为归并排序递归深度是log₂n，十亿级别的数据量深度也就30层左右，根本不会栈溢出。但迭代版本的归并排序依然值得掌握，因为它可以帮你看清楚归并排序的执行顺序，也能避免函数调用开销。

核心思路是：先把数组看作长度为1的n个有序子数组，然后两两合并成长度为2的有序子数组；再两两合并成长度为4的有序子数组……直到整个数组合并成一个有序数组。

public static void mergeSortIterative(int[] arr) { if (arr == null || arr.length < 2) return; int n = arr.length; int[] temp = new int[n]; // width 表示当前每个有序子数组的长度，从1开始，每次翻倍 for (int width = 1; width < n; width <<= 1) { // 每次处理两个长度为 width 的子数组 for (int left = 0; left < n; left += width << 1) { int mid = Math.min(left + width - 1, n - 1); int right = Math.min(left + (width << 1) - 1, n - 1); if (mid < right) { merge(arr, left, mid, right, temp); } } } }

这里面有几个边界条件需要特别小心。首先是mid和right都要做越界截断，因为数组长度不一定是2的幂，最后一段可能凑不齐。其次是即使右半区长度不为零，也要保证mid < right时才需要合并，否则右半区本来就是空的。初学的时候很容易在这里把下标写飞，后面我会在排查章节专门总结这些症状。

迭代版本还有一个隐藏的福利：它的合并顺序是确定的、平铺的，可以直观地看到每一轮合并的效果。这对调试和教学特别有帮助。而且你可以给每个width的循环加日志，观察数组状态的变化，这比盯递归调用栈要舒服得多。

2.3 工程级优化：小数组切插入排序、自然归并与Timsort

教科书里的归并排序能跑，但跑不快。真正被大规模工程采用的归并排序都是“杂交”过的。我自己实践中觉得最有效的三个优化方向，你可以在自己的项目里直接试试。

第一个优化是小数组使用插入排序。递归切分到子数组长度小于某个阈值（比如16、32或者64）时，不再继续递归，而是直接对这个小数组做插入排序。道理很简单，插入排序对接近有序的小数组非常友好，而且没有递归和合并的额外开销。这个阈值一般取16~64之间，具体的值需要根据你的数据规模benchmark一下。JDK的Arrays.sort里，对小数组就是用插入排序，阈值是47，就是一个经典的参考取值。

第二个优化是判断是否真的需要合并。如果左侧子数组的最大值已经小于等于右侧子数组的最小值，那说明两个子数组合起来已经整体有序了，直接跳过merge步骤。这个判断只需要比较arr[mid]和arr[mid+1]，O(1)的时间。对于接近有序的数据，这个优化能把时间直接砍掉一大截。这个技巧在很多实际项目里会出现，代价极小，收益却相当可观。

第三个优化是自然归并排序。经典的归并排序是“无脑”从中间切分，然后合并。但自然归并排序的思路是：先扫描一遍数组，找出所有已经有序的“自然分段”，然后对这些分段进行归并。如果数据本身已经部分有序，自然归并的初始分段会远大于1，合并轮数会变少，性能自然更好。这个思路就是著名的Timsort的核心基础。Python的sorted、Java的Arrays.sort（对象类型）、Android的列表排序，底层都是Timsort。如果你用的语言有内置Timsort，你其实每天都在享受归并排序变体的红利。

3. 拿一个具体数组完整推演：实操过程与核心环节实现

3.1 手把手模拟一次归并排序全过程

理论说再多，不如手推一遍。我用一个实际例子来演示：[38, 27, 43, 3, 9, 82, 10]。

第一步是递归切分。

• 初始区间[0, 6]，mid为3，切分成[38, 27, 43, 3]和[9, 82, 10]。
• 左区间[0, 3]，mid为1，切分成[38, 27]和[43, 3]。
• 区间[0, 1]，mid为0，切分成[38]和[27]。此时两个子数组都只有一个元素，递归到底。

然后开始一层层合并。

• 合并[38]和[27]：左右指针比较，27更小，放进去，然后38放进去，得到[27, 38]。
• 合并[43]和[3]：同理得到[3, 43]。
• 合并[27, 38]和[3, 43]：比较第一个元素，3最小取出来；再比27和43，取27；再比38和43，取38；最后取43。得到[3, 27, 38, 43]。

右半边同理。

• 区间[4, 6]，mid为5，切分成[9, 82]和[10]。
• 合并[9, 82]和[10]：得到[9, 10, 82]。

最后合并整个数组。

• 左有序区[3, 27, 38, 43]，右有序区[9, 10, 82]。
• 指针比较：3取左，9取右，10取右，27取左，38取左，43取左，82取右。
• 最终得到[3, 9, 10, 27, 38, 43, 82]。

这个推演过程你可以在纸上画成一颗递归树，每个节点的值代表当前区间合并后的有序结果。画一遍之后，你会对分治思想有肌肉记忆般的理解。

3.2 时间复杂度的严谨推导：主定理与最坏情况

我在前面说了T(n) = 2·T(n/2) + O(n)。这里用主定理（Master Theorem）严谨推导一下。

主定理的标准形式：如果T(n) = a·T(n/b) + f(n)，且f(n) = O(n^(log_b(a) - ε))，则T(n) = Θ(n^(log_b(a)))。在我们的例子中，a=2，b=2，所以log_b(a) = log₂2 = 1，而f(n) = O(n)，也就是说f(n)和n^(log_b(a))实际上是同阶的。这对应主定理的第二种情况：当f(n) = Θ(n^(log_b(a)) · log^k n)且k=0时，T(n) = Θ(n^(log_b(a)) · log^(k+1) n) = Θ(n log n)。

所以归并排序的时间复杂度严格是Θ(n log n)，而且这个结论不依赖数据分布，最好、最坏、平均情况都一样。这一点和快速排序有天壤之别。快排的平均是O(n log n)，但最坏是O(n²)。归并排序没有“运气不好”这一说。

那么空间复杂度呢？临时数组长度是n，递归调用栈深度是log₂n。所以总的空间复杂度是O(n + log n) = O(n)。注意，有些教材里说的O(n)其实忽略了递归栈的log n，但对渐进分析来说O(n)就是最终答案。如果你用的是迭代版本，递归栈没了，空间还是O(n)。空间换时间，这就是归并排序最核心的一个trade-off。

3.3 稳定性证明和它带来的连锁价值

稳定性在归并排序里是一次非常巧妙的“设计”。只要合并时取左侧元素的那个判断带上等于号，归并排序就能保证稳定。这是一个局部细节决定全局性质的好例子，代码里一行<=和一个<的区别，直接决定整个算法的适用场景。

稳定性带来最经典的应用是计算逆序对。所谓逆序对，就是满足i < j但arr[i] > arr[j]的数对。暴力法是嵌套循环O(n²)，但用归并排序可以在合并时顺便统计逆序对，时间复杂度直接降到O(n log n)。具体思路是：合并左右两个有序子数组时，如果右侧的某个元素先被拿出来，说明左侧当前指针到mid之间的所有元素都比它大，这些都比它大还排在前面的元素，每一个都构成一个逆序对。于是计数器加上mid - i + 1即可。

这个技巧在很多算法题和面试里特别常见，而且它不是生搬硬套，是真正利用了归并排序“合并两个有序序列”的过程特性。明白了这个，你就等于在归并排序这个地基上，又盖起了一座新楼。

4. 常见问题与排查技巧实录

4.1 边界条件写错：数组越界和“排序后丢失部分数据”

我见过最多的问题，集中在merge方法的下标处理上。最常见的错误有三个。

第一个是mid计算错误，直接用(left + right) / 2，在大数组时可能溢出为负数，直接ArrayIndexOutOfBoundsException。这个我在前面提过，解决方案就是left + ((right - left) >> 1)。

第二个是merge最后拷贝回原数组时，游标没有重置。很多人写完两个while之后，直接把临时数组从0开始往原数组拷：

for (int k = 0; k < right - left + 1; k++) { arr[left + k] = temp[k]; }

这段逻辑其实是对的。但如果你在merge方法开头用了t = 0作为临时数组游标，合并完之后忘了把t归零，或者拷贝时用了临时数组里从left开始的位置，数据就错位了。正确做法是temp[t++]从头写入，拷贝时也从0开始，或者拷贝时直接遍历arr的下标区间。两种思路不能混。

第三个是递归区间划分时下标重叠或漏项。正确写法是sort(arr, left, mid, temp)和sort(arr, mid + 1, right, temp)，左闭右闭区间。如果你手滑写成sort(arr, left, mid - 1, temp)去处理左半区，或者右边写成sort(arr, mid, right, temp)，就会导致元素被遗漏或者无限递归。这种bug的排查方法很简单，打印每个递归调用的left、mid、right，一眼就能看出来哪里对不上。

4.2 稳定性的坑：你以为稳了，实际上没稳

稳定性是归并排序的招牌，但也是很多人栽跟头的地方。你只要在merge的比较条件里把一个<=改成<，稳定性就没了。而且这种错误不会让你得到错误的结果，数组照样能排好序，只有当你对“成对数据”做多轮排序时，才会发现第二轮的排序结果顺序不对。

排查方法：造一组带序号的数据，比如[{1, "a"}, {2, "b"}, {1, "c"}]，按第一个字段排序，然后检查相同第一个字段的元素，第二个字段的先后顺序是否和排序前一致。如果{1, "c"}跑到{1, "a"}前面了，恭喜你，你踩到稳定性的坑了。

还有一种场景容易忽略稳定性：如果你拿归并排序去排一个对象数组，但对象的equals和compareTo方法没有保持一致，排序结果看上去稀里哗啦。这其实不是归并排序的问题，是对象自身的比较逻辑出问题了。

4.3 性能陷阱：临时数组频繁分配和递归中的无效合并

用归并排序结果跑得巨慢，往往不是算法本身的问题，而是实现细节拖了后腿。

第一个性能杀手是在merge内部new临时数组。每层递归都new一个，n=10万的时候你可能new了几十万个数组对象，GC直接被拖垮。解决方案是像我在前面代码里写的那样，在最外层申请一个足够大的临时数组，传引用进递归。实测下来，只改这一个点，性能就能提升一个数量级。

第二个性能杀手是对小数组无脑递归到底。当子数组长度小到5、10的时候，归并排序的函数调用开销和合并操作反而比插入排序更慢。处理方式就是前面说的阈值判断，小于阈值直接insertionSort。我自己实测，阈值设在32附近效果不错，但具体数字取决于你机器的缓存和JIT状态，建议写个benchmark自己跑一遍。

第三个性能杀手是没有利用“已经有序”的连续性。如果arr[mid] <= arr[mid+1]，左右两个子数组拼起来其实已经有序，直接return，省掉一次完整合并。在近似有序的数据上，这个优化效果非常显著。

4.4 归并排序问题排查速查表

为了方便你以后直接查，我把这些常见问题整理成一个速查表，遇到症状直接对应找原因。

这张表基本覆盖了我平时帮同事和网友排查归并排序问题会遇到的所有情况。你在实际项目里遇到其他怪问题时，最有效的通用排查手段还是两条：一是打印区间下标，二是用极小数据（5-10个元素）做逐步跟踪。

5. 归并排序的思想还能用在哪：扩展与变体

5.1 外部排序：内存装不下的时候怎么办

前面讲过归并排序的空间复杂度是O(n)，需要一整块和原数组等长的内存。那如果数据量远远超过内存容量，比如要对几百GB的日志文件排序，连一次性载入内存都做不到，该怎么办？

答案是外部排序，而它的核心依然是归并的思路。经典做法是：把大文件切分成很多小块，每一块大到内存能装下，然后对每个小块在内存里排序，写回磁盘形成有序的临时文件。接着把这些有序文件做多路归并，利用一个堆或者优先级队列维护当前每个文件的头部元素，每次取出最小的，继续读下一个。这种k路归并就是归并排序在“内存放不下”场景下的自然延伸。

我第一次接触外部排序是在处理大数据量的日志分析时，当时理解了这个思路之后，再去看看MapReduce的shuffle sort，发现底层逻辑惊人的一致——分而治之，局部有序，多路合并。

5.2 并行归并：多线程/多机场景下的拆分方式

归并排序的“分治”结构天然适合并行。两个半区的排序互不依赖，完全可以丢到两个线程甚至两台机器上去跑。唯一的串行瓶颈在最后的合并阶段，但合并本身是线性的，而且可以用双指针并行扫描。

实际做并行化的时候，最直接的方式是递归的前半部分用线程池提交子任务，然后等两个子任务都完成后再合并。要注意的是线程数不能无脑开，因为线程切换和合并的带宽开销可能反而拖慢速度。比如8核机器你开到几十个线程去排序100万个数，性能大概率不如单线程优化好的归并排序。这个领域，可以用Fork/Join框架去实现和调优。

5.3 归并排序与链表排序的特殊缘分

数组的归并排序需要O(n)额外空间，但链表归并排序有个巨大的优势：链表的合并不需要额外空间，只需要修改指针。所以对链表做归并排序时，空间复杂度可以做到O(1)（如果不算递归栈的话）。这一点让归并排序成了链表排序的首选算法。

链表版归并排序的递归思路不变，找中点需要用快慢指针，合并时则是链表的经典双指针操作。面试里经常出现的“对链表排序（要求O(n log n)时间、O(1)额外空间）”这道题，标准答案就是链表上的归并排序或自底向上归并。我自己在实现链表归并排序时踩过一个很有意思的坑：快慢指针找中点时，要把前一个链表的尾巴置空，否则两个子链表没有断开，合并时会形成环。这个细节非常容易忽视，值得记住。

5.4 逆序对、区间统计与归并思想的更深延伸

归并排序的“合并两个有序序列”的过程，实际上是在线性时间内做“跨左右”的信息统计。最典型的例子就是逆序对计数，我已经在前面说过了。但同样的思路还可以推广到很多问题上：统计每个数左边有多少个数比它大/小、处理区间求和类问题、甚至可以配合树状数组做更复杂的离线查询。

这类问题有一个共同特征：它们都需要处理“一个元素和前面所有元素的关系”。暴力法是嵌套循环，而分治的办法，是把“前面所有元素”这个集合变成“左边半个数组”和“右边半个数组”分别处理，最终在合并时一次性统计跨左右两半的所有关系。这就是归并排序思想真正值钱的地方。你一旦掌握了这个模式，再去看CDQ分治这类高级算法时，会发现似曾相识——它们本质上都在用“分治后合并时顺手统计跨区间的信息”这一招。

写在最后的一些经验

以我个人的习惯，如果在面试或者实际项目中要写排序，我会先问自己三个问题：数据量多大？内存够不够？要不要稳定性？如果数据量小，直接插入排序；如果数据量大、内存宽裕、又要求稳定，归并排序是闭眼选的那个；如果数据量大、内存紧张而且不在乎稳定性，那快排或者堆排可能更合适。

我还想分享一个自己实践过很多次的小技巧：调试归并排序时，不要用太大数组调。拿5~10个元素的数组，然后在每层merge结束之后打印整个数组的状态。你会非常直观地看到一个混乱的数组是如何一步步变成有序的，这比任何debug工具都管用。很多网上问“为什么我的归并排序排不出来”的人，用这个方法一看就发现自己哪里写错了。

归并排序本身只是算法海洋里的一小片水域，但围绕它的分治思想、稳定性设计、外部排序延伸、逆序对应用，这些才是真正值得反复琢磨的宝藏。把这个算法吃透了，你再看很多“高级”的数据结构和算法，会发现它们不过是在不同场景下，用同样的思维框架去解决新问题而已。