相信很多朋友在准备面试或做算法练习时，都绕不过归并排序（Merge Sort）这道坎。它不像冒泡、选择排序那样“一眼就能看懂”，但却是真正值得花时间吃透的算法之一。这篇文章不打算泛泛而谈，而是基于我实际写代码、调 bug 的经验，把归并排序从原理到 Java 实现完整地拆一遍，包括那些文档里不会写的细节和坑。
归并排序的核心思想只有八个字：分而治之，合而为一。它先把大数组拆成小数组，拆到不能再拆（只剩一个元素），然后再把有序的小数组合并成大数组，最终得到一个完全有序的序列。这个过程是通过递归实现的，所以理解递归的调用栈，是掌握归并排序的第一个门槛。
这篇文章适合正在学数据结构与算法的同学、准备技术面试的开发者，以及任何想真正理解“分治思想”的读者。读完你不仅能写出能跑的代码，还能在面试中把复杂度、稳定性、优化方案讲得明明白白。
1. 算法思想与设计思路
1.1 用“拆信封”理解分治策略
想象你在整理一叠乱序的试卷，正常的做法是一张一张地排，速度很慢。归并排序的思路则是：把这叠试卷从中间分成两半，每半再分成两半，直到每份试卷只有一张。此时“每一叠”天然就是有序的（只有一张嘛）。接下来，把相邻的两叠小试卷按照学号从小到大合并成一叠，合并的结果依然有序，然后继续合并更大的两叠……直到最终还原成一整叠有序的试卷。
这个过程体现了分治法的三个关键步骤：
- 分解（Divide）：把规模为 n 的问题拆分成两个规模约为 n/2 的子问题；
- 解决（Conquer）：递归地解决每个子问题，当子问题规模小到 1 时，直接返回；
- 合并（Merge）：将两个已排序的子序列合并成一个有序序列。
归并排序“分”的阶段没有做任何比较和交换，真正的排序动作发生在“合”的阶段。这也是它区别于快速排序的地方：快排是“先大体排好，再递归细分”，归并是“先拆到底，再逐步合并”。理解这个顺序非常关键，因为很多同学写完代码后发现数组还是乱的，多半是 merge 过程比较的逻辑写错了。
1.2 为什么选择递归实现
归并排序天然适合递归描述：每次分解都是同样结构的子问题。用递归写起来代码简洁、逻辑清晰。当然，递归也意味着额外的函数调用开销和栈空间消耗，但这是归并排序固有的成本，后面我会讲如何规避。
从工程角度看，归并排序的三大特性决定了它不可替代的价值：
- 时间复杂度稳定：无论数组原本是正序、逆序还是乱序，时间复杂度永远是 O(n log n)。这一点胜过快速排序的最坏情况 O(n²)；
- 稳定性：排序后相等元素的相对位置不变，这在多关键字排序场景（比如先按姓名排，再按成绩排）中非常关键；
- 适合外部排序：当数据量大到内存放不下（比如 10GB 文件排序），归并排序可以通过“外存 + 多路归并”来完成，这一点其他 O(n log n) 的排序算法很难做到。
不过，归并排序也不是万能的。它的缺点同样明显：需要 O(n) 的额外空间来存放临时数组。所以它属于“用空间换时间”的典型代表。在实际项目中，对基本数据类型排序，JDK 的Arrays.sort()用的是双轴快速排序，而对对象类型排序，用的是归并排序（TimSort 本质上也是归并的变体），这个细节本身就很说明问题。
2. 复杂度分析与适用场景
2.1 时间复杂度的直观推导
归并排序的时间复杂度可以这样估算：每一轮归并，都需要扫描整个长度为 n 的数组，做 n 次比较和赋值；一共需要归并 log₂n 轮（因为每轮规模翻倍）。所以总操作次数 = n × log₂n。
这里用具体的数字感受一下规模差异。对 100 万个元素排序：
| 算法 | 复杂度 | 操作次数（约） | 感受 |
|---|---|---|---|
| 冒泡排序 | O(n²) | 10¹² | 慢到无法接受 |
| 归并排序 | O(n log n) | 2×10⁷ | 毫秒级完成 |
这就是为什么数据量大时，我们必须在 O(n log n) 级别的算法里做选择。还有一个容易搞错的知识点：归并排序的效率与初始数据顺序无关。不管输入是 already sorted 还是 completely reversed，它都老老实实地拆、合、比，所以最好、最坏、平均时间复杂度都是 O(n log n)。这也是它被称作“稳定性能”算法的原因。
2.2 空间复杂度与稳定性分析
空间复杂度方面，归并排序需要一个长度为 n 的辅助数组，因此额外空间为 O(n)。再加上递归调用时栈的深度为 log₂n，总的空间占用为 O(n + log n) ≈ O(n)。面试时常常会问“能否将空间复杂度降为 O(1)”，答案是可以的，那就是原地归并排序（in-place merge sort），但实现极其复杂且常数因子巨大，实际工程中没人这么干。我的建议是：面试时提一句“可以通过原地归并降低空间，但会使算法变得复杂且变慢”，展示你知道这个知识点即可，不要主动深入。
稳定性是指：如果两个元素相等，排序后它们的先后顺序不变。归并排序为什么稳定？关键在于 merge 阶段，当左半部分的元素 <= 右半部分的元素时，我们优先取左半部分的元素。这里的 <= 保证了相等元素中左侧的那个会先被放入结果数组，顺序不被打乱。如果这里写成了 <，则相等时会把右侧元素放到左侧元素前面，稳定性就丢失了。这是一个非常隐蔽的 bug 点，后面代码部分我会特别标出来。
2.3 什么场景适合用归并排序
根据我自己的项目经验，归并排序在以下几种场景中表现突出：
- 链表排序：链表的随机访问代价高，快排的 partition 操作涉及大量交换，效率不佳；而归并排序只需要修改指针，天然适合链表结构；
- 大数据外部排序：比如数据库的排序算子、分布式计算框架中的 shuffle 阶段，都大量使用归并思路，因为数据在磁盘上无法整体载入内存，必须分块排序后归并；
- 对象数组排序：Java 中对对象的默认排序要求稳定，所以 JDK 内部选择归并排序（或 TimSort）作为实现基础；
- 需要保证稳定性的多字段排序：比如先按成绩降序、但成绩相同的保持原来的名次顺序，此时归并排序是安全选择。
反之，如果数据规模小（几百个元素以内）、对空间敏感（比如嵌入式环境）、且不要求稳定性，那么插入排序或快排的变体可能更合适。归并排序在小数组上反而因为递归和额外数组的开销，性能不如插入排序，这也是很多标准库会在数组长度小于某个阈值时切换排序策略的原因。
3. Java 实现与测试
3.1 完整代码：递归版归并排序
直接上代码，这是最经典的递归实现：
public class MergeSort { /** * 归并排序入口 */ public static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 直接传入整个区间 process(arr, 0, arr.length - 1); } /** * 递归处理 [left, right] 区间 */ private static void process(int[] arr, int left, int right) { if (left == right) { return; // 只剩一个元素，天然有序 } int mid = left + ((right - left) >> 1); // 防溢出写法 process(arr, left, mid); // 左半部分排好序 process(arr, mid + 1, right); // 右半部分排好序 merge(arr, left, mid, right); // 合并 } /** * 合并两个有序区间 [left, mid] 和 [mid+1, right] */ private static void merge(int[] arr, int left, int mid, int right) { int[] help = new int[right - left + 1]; // 临时数组 int i = 0; // help 的指针 int p1 = left; // 左半区指针 int p2 = mid + 1; // 右半区指针 // 谁小填谁，注意用 <= 保证稳定性 while (p1 <= mid && p2 <= right) { help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } // 左半区有剩余，直接拷贝 while (p1 <= mid) { help[i++] = arr[p1++]; } // 右半区有剩余，直接拷贝 while (p2 <= right) { help[i++] = arr[p2++]; } // 写回原数组 for (int j = 0; j < help.length; j++) { arr[left + j] = help[j]; } } }几处关键细节解释一下：
left + ((right - left) >> 1)：这种写法等同于(left + right) / 2，但避免了 left 和 right 都很大时中间值溢出的问题。位运算>> 1表示右移一位，相当于除以 2，且由于优先级问题，外层必须加括号；- merge 中三个 while 循环：第一个循环把两家中较小的元素依次填入 help，一旦某一边耗尽，剩下两个循环把另一边的剩余元素全部搬过去。这三个循环缺一不可，少了后者会丢元素；
- 稳定性体现在
arr[p1] <= arr[p2]这个判断：当相等时取左边元素，这样相同数值的前后顺序保持不变。
3.2 测试验证：从无序到有序
写一段测试代码来验证：
public class MergeSortTest { public static void main(String[] args) { // 典型测试用例 1：常规乱序 int[] arr1 = {38, 27, 43, 3, 9, 82, 10}; MergeSort.mergeSort(arr1); System.out.println(Arrays.toString(arr1)); // 输出：[3, 9, 10, 27, 38, 43, 82] // 测试用例 2：已经有序的数组 int[] arr2 = {1, 2, 3, 4, 5}; MergeSort.mergeSort(arr2); System.out.println(Arrays.toString(arr2)); // 输出：[1, 2, 3, 4, 5] // 测试用例 3：完全逆序 int[] arr3 = {9, 8, 7, 6, 5, 4}; MergeSort.mergeSort(arr3); System.out.println(Arrays.toString(arr3)); // 输出：[4, 5, 6, 7, 8, 9] // 测试用例 4：含有大量重复元素 int[] arr4 = {5, 3, 5, 2, 5, 1, 5}; MergeSort.mergeSort(arr4); System.out.println(Arrays.toString(arr4)); // 输出：[1, 2, 3, 5, 5, 5, 5] } }我用上面这个用例从最早写归并到现在，跑过无数遍。每次看到{38, 27, 43, 3, 9, 82, 10}变成{3, 9, 10, 27, 38, 43, 82}，都能更直观地理解递归的拆合过程。建议你也亲手在纸上把{5, 3, 8, 1}的递归过程画一遍：第一层拆成{5,3}和{8,1}，第二层再拆成{5}、{3}、{8}、{1}，然后从四个单元素开始，逐步合并为{3,5}、{1,8}，最终合并为{1,3,5,8}。把这张图画出来，归并排序就算学懂一半了。
3.3 结合 IDEA 查看递归过程（附加价值）
如果你用的是 IntelliJ IDEA，Debug 模式下有一个很实用的功能：在process方法的方法签名行打上断点，然后选择 “Drop Frame” 或直接观察调用栈（Frames）面板，就能看到递归调用的完整路径。就像剥洋葱一样，一层一层进入然后又一层一层返回，这对理解递归极其有帮助。
4. 常见问题与实操心得
4.1 面试高频问题集锦
问题一：归并排序的时间复杂度为什么一定是 O(n log n)？
回答思路：每一轮归并需要遍历全部元素 n 次，而数组长度从 n 到 1 的对数压缩需要 log₂n 轮。所以总次数是 n × log₂n。无论数据好坏，拆分的结构不变，因此这个复杂度是稳定的。
问题二：归并排序是稳定的吗？如何实现稳定性？
回答思路：是稳定的。关键在 merge 阶段，当左右两边的元素相等时，先取左半边的元素，用<=而不是<就能确保稳定性。如果面试官追问原因，可以引申到“多关键字排序”的场景。
问题三：归并排序的空间复杂度是多少？可以优化吗？
回答思路：常规实现是 O(n)，因为要额外的辅助数组。可以优化的是复用同一个辅助数组（下面我会写），但无法做到 O(1) 且保持 O(n log n) 的性能。Node 节点排序可以用原地合并技巧，不过实现较复杂。
问题四：为什么 JDK 对基本类型排序用快排，对对象排序用归并？
回答思路：基本类型排序不需要稳定性，快排的空间利用更好（栈空间），而对象的 equals 比较代价相对高，稳定性是个重要特性（比如对 web 应用中的对象按多个字段排序），归并排序是更好的选择。
4.2 真实踩坑：临时数组每次新建的性能陷阱
很多初学者写 merge 时，会在每次合并时new int[right - left + 1]。这在数据量小时问题不大，但是当数组长度达到千万级别时，频繁创建和销毁大数组会带来重大的内存分配和 GC 开销。实测中，数据规模为 1000 万个 int（约 40MB）时，每次 new 的实现比复用辅助数组的实现慢了大约 30%~50%，差距非常明显。
优化方案是：在主函数中一次性创建好辅助数组，通过下标区间复用它：
public class MergeSortOptimized { public static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int[] help = new int[arr.length]; // 只创建一次 process(arr, help, 0, arr.length - 1); } private static void process(int[] arr, int[] help, int left, int right) { if (left == right) { return; } int mid = left + ((right - left) >> 1); process(arr, help, left, mid); process(arr, help, mid + 1, right); merge(arr, help, left, mid, right); } private static void merge(int[] arr, int[] help, int left, int mid, int right) { int i = left; // 直接从 left 开始写 int p1 = left; int p2 = mid + 1; while (p1 <= mid && p2 <= right) { help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= mid) { help[i++] = arr[p1++]; } while (p2 <= right) { help[i++] = arr[p2++]; } // 将 help 中 [left, right] 区间拷回 arr for (int j = left; j <= right; j++) { arr[j] = help[j]; } } }看懂这版和上一版的差异了吗？关键变化是 help 数组的索引直接用原数组的下标位置，而不是从 0 开始。这样每次归并写回时，只需循环把[left, right]这段拷回去即可。这不仅是性能优化，也简化了对索引的理解。
4.3 归并排序的延伸：从“递归”到“迭代”
递归版本虽然好懂，但深度太大时（比如排一百万元素），函数调用栈可能成为问题。不过实际递归深度只有 log₂n ≈ 20 层，对 Java 默认栈深度来说绰绰有余，所以你不需要担心栈溢出。但作为知识扩展，你可以尝试用迭代（自底向上）的方式实现归并排序：
- 第一轮，两两合并，步长为 2；
- 第二轮，四四合并，步长为 4；
- 以此类推，直到步长超过数组长度。
迭代版的代码不写了，但思想值得体悟：递归版是“从上往下拆”，迭代版是“从下往上合”，两者最终殊途同归。面试中如果你能提一句“我会用自底向上迭代法规避递归栈开销”，会加分不少。
4.4 归并思想在工程中的真实应用
归并排序不仅仅是一个课堂算法。我实际参与过的项目中，遇到过这样一个需求：需要对一个 4GB 的大文件按某列排序，内存只有 2GB。方案就是分块读入排好序再归并，这正是归并排序思想的工程化应用。
具体做法是：
- 将大文件拆分为若干个可以完全载入内存的小块（比如每块 256MB）；
- 对每个小块使用 Java 的
Arrays.sort（内部是快排）排序，然后写入临时文件； - 最后将这些有序的小文件两两（或多路）归并成一个完整有序的大文件。
这种场景在离线数据处理、日志分析中非常常见。如果你理解了归并排序的 Merge 过程，面对这种需求时就能马上想到解决方案，而不是重新造轮子。
4.5 一个容易忽略的细节：小数组时改用插入排序
在 JDK 的Arrays.sort源码中，当被排序的数组长度小于某个阈值（比如 47）时，会改用插入排序而非归并或者快排。原因很简单：小数组上递归和额外数组的常数开销太大，插入排序反而更快。如果你想优化归并排序的性能，可以在process方法中加一个长度判断：
if (right - left <= 15) { insertionSort(arr, left, right); return; }这样数组小到一定程度时，就不再继续拆分，直接走插入排序。这个改动不影响时间复杂度，但在实际性能测试中，对随机小数组能带来近一倍的提升。
写在最后的一点体会
归并排序是我在学数据结构时认为“最容易写错但一旦理解就再也不会忘”的算法。它的代码量不大，但包含递归、分治、双指针、稳定性这些重要的计算机思维。如果你正在刷题或准备面试，建议你不仅把它背下来，而是亲手画递归树、跑测试用例、对比优化前后的性能数据。我在实战中的体会是：真正理解一个算法的最快方式，永远是“用笔走一遍 + 让代码跑一遍 + 和别人讲一遍”。如果能做到这三步，归并排序这块硬骨头就彻底啃下来了。
最后再分享一个小技巧：你可以在本地写一段随机数生成器，生成 100 万条随机整数，分别用普通版和优化版跑一遍，看看耗时差异。实测下来，复用辅助数组的速度真的能快不少——而这种细节，恰恰是面试官区分“背过答案”和“真正理解”的关键。
