如果只能选一个排序算法来讲清楚什么是分治思想，我会选归并排序。它的时间复杂度稳定在 O(nlogn)，无论数据本来是什么样，表现都不会退化，这是快排在极端情况下都比不了的。更重要的是，归并排序不只是“一个排序算法”，它的合并思路直接延伸出了外部排序、逆序对统计、链表排序等高阶玩法，几乎是算法面试里最常被拿来深挖的知识点之一。

这篇文章适合两类人：一类是刚学完冒泡、选择、插入排序，想系统理解分治排序的初学者；另一类是面试前想把这套东西彻底讲明白、把变体真正搞懂的求职者。我会把思路、复杂度推导、手写代码、常见坑和优化方案全部拆开讲，争取让你看完就能写出一份干净的实现，也能把 O(nlogn) 这个复杂度说到别人点头。

1. 先弄明白归并排序到底在“归并”什么

1.1 分治三步走：拆、排、合

归并排序的英文叫 Merge Sort，核心动作就两个：归并和排序。但真正理解它之前，得先接受一个看起来很“绕”的设定：我们要把一个乱序数组变有序，不直接对整个数组下手，而是先把它切成两半，把左半部分排好序、右半部分排好序，最后再把两个有序半区合并成一个有序整体。

这个过程就是典型的分治（Divide and Conquer）：分解（Divide）、解决（Conquer）、合并（Combine）。

具体到归并排序，就是三步：

1. 拆：把数组从中间位置一分为二，得到左右两个子数组。
2. 排：递归地对左右两个子数组分别做归并排序，直到子数组只剩一个元素。一个元素天然有序，不用再排。
3. 合：把两个已经各自有序的子数组合并成一个更大的有序数组。

这也是为什么叫“二路归并”——每次合并的都是两个有序序列。你可以理解为两堆已经按从小到大排好的扑克牌，现在要把它们合在一起还是有序的，做法就是每次从两堆牌的顶部各取一张，比较大小，把更小的那一张放到结果堆里，然后继续。

“拆”这个动作看起来简单，里面藏着一个关键细节：拆分不是把数据复制成两个新数组，而是用索引来“假装切开”。我们操作的是同一个数组，只是通过 left、mid、right 三个下标把它的逻辑范围分成两段。这样做的好处是不用额外复制数据，省内存也省时间。很多初学者第一次写归并排序时总想着把左半部分拷到一个新数组，再拷右半部分，最后再合并成一个新数组——这样也能跑通，但完全没有必要，代码还会变得很啰嗦。

1.2 合并两个有序数组，是整个算法的灵魂

合并这一步，可以说是归并排序真正的“技术含量”所在。前面那些拆分、递归，本质上都是在为合并创造前提条件。如果给一个完全乱序的数组直接做合并，是没有意义的——只有左右两半都已经有序，合并过程才能在线性时间内完成任务。

合并操作本身很短，但边界条件特别容易写错。它的核心逻辑是：用两个指针 i 和 j 分别指向左子数组和右子数组的开头，比较 arr[i] 和 arr[j] 的大小，把较小的元素放进一个临时数组，然后让对应的指针往后移动一格。重复这个过程，直到某一方的元素被取完，再把另一方的剩余元素直接按顺序拷进临时数组。

为什么剩余元素可以直接拷？因为左右两个子数组在进入合并之前都已经是有序的，所以在某一方耗尽之后，另一方剩下的元素不仅有序，而且全都比已经放入临时数组的元素大，直接追加就不会有任何问题。

合并完成之后还需要一步收尾动作：把临时数组里的元素写回原数组的对应位置。这一步忘了做，或者写回的位置搞错，整个排序结果就是乱的。用生活里的场景来理解，合并就像你把两列各自排好队的同学合并成一列更长的队，一边的同学依次出队比较身高，矮的先进新队列，最后一边没人了，另一边剩下的同学按顺序全部进入新队列——这时你还要让这支新队伍站回原来的教室位置，才算真正完成合并。

2. O(nlogn) 是怎么算出来的：递归式与递归树

2.1 从递归式 T(n) = 2T(n/2) + O(n) 说起

归并排序的时间复杂度，不能只靠“感觉说好像挺快”来糊弄，得能推导出来。推导的起点是一个递归式。

如果一个规模为 n 的问题，被拆成两个规模为 n/2 的子问题，分别解决它们各需要一个 T(n/2) 的时间；在合并这两个子数组时，要把所有 n 个元素都过一遍并放进临时数组，所以合并成本是 O(n)。于是我们有：

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

这个式子读起来就是：排序 n 个元素的时间，等于排序左半边的时间加上排序右半边的时间，再加上合并两边花费的线性时间。

那递归的底在哪里？当 n = 1 时，一个元素已经有序，不需要做任何排序和合并操作，所以 T(1) = O(1)。

有了递推式和终止条件，就可以开始展开这个递归式，一层层看它到底累加出了什么结果。

2.2 用递归树和主定理交叉验证

先拿递归树来展开。假设 n = 8，画一下递归的层次：

• 第 0 层：整个数组长度为 8，合并这一层的数据需要 O(8) 时间。
• 第 1 层：分成两个长度为 4 的子数组，每个子数组合并需要 O(4)，两个合起来还是 O(8)。
• 第 2 层：分成四个长度为 2 的子数组，每个合并需要 O(2)，四个合起来还是 O(8)。
• 第 3 层：分成八个长度为 1 的子数组，每个合并需要 O(1)，八个合起来还是 O(8)。

看出规律没有？每一层的合并总代价都是 O(n)，因为不管这一层有多少个子问题，它们的规模加起来正好就是 n。而递归树一共有多少层？每次规模减半，从 n 减到 1，需要 log2(n) 次拆分，所以层数是 O(logn)。层数乘以每层的代价，就得到了总复杂度：

T(n) = O(logn) × O(n) = O(nlogn)

这个推导很直观，也不依赖任何公式。如果你想用更规范的工具交叉验证，可以上主定理（Master Theorem）。对于 T(n) = aT(n/b) + f(n)，这里 a = 2，b = 2，f(n) = O(n)，那么 log2(2) = 1，f(n) 的阶正好是 n^1，落入主定理的第二种情况，直接得出 T(n) = O(nlogn)。两个方法结论一致，说明这个结果非常可信。

2.3 为什么归并排序的最好、最坏、平均都是 O(nlogn)

这一点是归并排序区别于快排的重要特征。快排在最坏情况下会退化到 O(n^2)，因为如果每次选的基准都不巧，分区会极端不均匀，一边总是空的一边总是满的。但归并排序不会。

归并排序的分裂永远是从中间一分为二，跟数据的初始顺序没有关系。不管数组已经完全有序、完全逆序，还是乱序到离谱，拆分路径都一样，递归树的层数都一样，每层的合并代价也都是 O(n)。所以它的最好、最坏、平均时间复杂度稳定地保持在 O(nlogn)，没有任何输入能把它拖下水。

这种“输入不敏感”的特性，在实践中意味着性能可预期。不需要担心某批数据恰好踩中退化场景。

空间复杂度也要单独说清楚。归并排序不是原地排序，因为合并阶段需要一块额外的临时数组，大小跟待排序区间一致，最大时是 n，所以额外空间是 O(n)。递归调用本身还会占用系统栈，栈的深度等于递归树的层数 O(logn)。把临时数组和调用栈加起来，总体额外空间是 O(n + logn)，渐进意义上就是 O(n)。这也是归并排序经常被拿来和快排对比的一个点：快排的额外空间平均是 O(logn)，归并是 O(n)，内存敏感的场景下归并就比较吃亏。

3. 手把手写一个干净的归并排序

3.1 一份可以直接跑的 JavaScript 实现

直接上代码。我用 JavaScript 写，因为它在算法面试和前端场景里覆盖很广，而且又没有真正的“数组切片排序”这种系统函数来干扰思路。各位用 Python、Java 的也能看懂，逻辑完全一致。

function mergeSort(arr, left = 0, right = arr.length - 1) { if (left >= right) { return; } const mid = (left + right) >> 1; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } function merge(arr, left, mid, right) { const temp = new Array(right - left + 1); let i = left; let j = mid + 1; let 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++]; } for (let m = 0; m < temp.length; m++) { arr[left + m] = temp[m]; } }

这段代码是标准的二路归并。注意几个细节：mid 用(left + right) >> 1计算，等于Math.floor((left + right) / 2)，但写法更简洁。递归终止条件是left >= right，等于说区间里只有一个元素甚至没有元素时就不动了。

合并时临时数组的长度是right - left + 1，也就是当前区间的元素个数。两个 while 循环分别处理“某一方先走完”的情况，最后再把临时数组内容从left开始逐个写回原数组。很多人写错的就是最后这一步，写回时用arr[m] = temp[m]，而temp的下标是从 0 开始的，原数组的位置却是从left开始的，不对齐就直接把排序结果写飞到别的位置上。

3.2 关键边界与稳定性细节

写归并排序最常见的错误集中在几个边界上，我列一下实测容易翻车的地方。

第一，空数组和单元素数组。mergeSort([])执行时，left = 0，right = -1，触发left >= right直接返回，没问题。但如果你的递归终止条件写的是left === right，空数组就会出问题，所以写大于等于更稳妥。

第二，mid 的计算。不要写成(left + right) / 2然后直接当索引用，如果结果是浮点数，数组访问会得到 undefined，合并时会莫名报错或排错序。稳妥做法是取整，>> 1或者Math.floor都可以。

第三，稳定性。归并排序天然是稳定的，关键就在这一句：

if (arr[i] <= arr[j]) {

注意是小于等于，不是小于。如果写成小于，当左右两边的元素相等时，我们会先把右边那个放进临时数组，而右边元素原本在整体顺序中位于左边元素之后，这会破坏相同元素的相对位置，稳定性就丢了。虽然对于纯数字数组来说，稳定性好像无所谓，但对按多个字段排序的对象数组很有意义。比如先按姓名排好序，再按年龄做稳定排序，年龄相同的还是要保持第一次排序后的相对顺序，这时候稳定排序就很重要了。

第四，辅助空间的分配。上面这段代码每次 merge 都new一个数组，对演示没问题，但数据量一大，GC 会很心疼。后面第 4 章我会说怎么优化。

3.3 面试常见变形：返回逆序对数量

归并排序最有名的一个变体是计算逆序对。所谓逆序对，就是数组中一对索引 i < j，但 arr[i] > arr[j] 的元素对。比如[3, 1, 2]就有两对逆序对：(3,1) 和 (3,2)。

最朴素的做法是双重循环，O(n^2)。但用归并排序，可以在合并阶段顺便数出来，复杂度降到 O(nlogn)。原理是这样的：当我们在 merge 时发现arr[i] > arr[j]，说明从左半区当前位置 i 到左半区末尾 mid 的所有元素，都比 arr[j] 大，而且它们的索引都在 j 之前，所以一共构成了mid - i + 1个逆序对。

let count = 0; function mergeSortCount(arr, left = 0, right = arr.length - 1) { if (left >= right) { return; } const mid = (left + right) >> 1; mergeSortCount(arr, left, mid); mergeSortCount(arr, mid + 1, right); mergeCount(arr, left, mid, right); } function mergeCount(arr, left, mid, right) { const temp = new Array(right - left + 1); let i = left; let j = mid + 1; let k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { count += mid - i + 1; temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } for (let m = 0; m < temp.length; m++) { arr[left + m] = temp[m]; } }

每次递归调用都会往全局 count 里累加，最终就得到了整个数组的逆序对总数。这个题在很多算法面试里以各种包装出现，本质上考的就是对归并合并过程的理解——你只有真正明白右半区某个元素能被左半区哪些元素“碾压”，才能写出这行计数逻辑。

4. 归并排序的三个实用优化

4.1 小数组切到插入排序

归并排序的递归开销不小。每次函数调用都要保存上下文、压栈、返回，当子数组长度很小，比如只有 4 个、8 个元素时，递归调用的成本甚至可能高过直接做一次简单插入排序的成本。所以工程实践里普遍的做法是设定一个阈值，子数组长度小于等于它时，放弃继续递归，改用插入排序。

这个阈值没有绝对标准，我习惯取 10 到 16。在递归函数开头加一句：

if (right - left <= 10) { for (let i = left + 1; i <= right; i++) { const cur = arr[i]; let j = i - 1; while (j >= left && arr[j] > cur) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = cur; } return; }

插入排序在几乎有序的小数组上表现极好，而且本身是稳定排序，不会破坏归并排序的稳定性。实测下来，对 10 万量级随机数组，这个优化能带来肉眼可见的提升，因为少了几万次递归调用和临时数组创建。

4.2 复用辅助数组，别让 GC 背锅

原始实现里，每次 merge 都创建一个新数组。递归到叶子附近时，合并操作非常频繁，短时间会创建大量小数组，垃圾回收的压力会变得很大。优化思路很朴素：提前一次性分配一个和原数组等长的辅助数组，每次合并都用同一块内存。

举个例子：

function mergeSort(arr) { const helper = new Array(arr.length); sort(arr, 0, arr.length - 1, helper); } function sort(arr, left, right, helper) { if (left >= right) return; const mid = (left + right) >> 1; sort(arr, left, mid, helper); sort(arr, mid + 1, right, helper); merge(arr, left, mid, right, helper); } function merge(arr, left, mid, right, helper) { for (let i = left; i <= right; i++) { helper[i] = arr[i]; } let i = left; let j = mid + 1; let k = left; while (i <= mid && j <= right) { if (helper[i] <= helper[j]) { arr[k++] = helper[i++]; } else { arr[k++] = helper[j++]; } } while (i <= mid) arr[k++] = helper[i++]; while (j <= right) arr[k++] = helper[j++]; }

这个版本的思路是从原数组复制到辅助数组，再从辅助数组合并回原数组，省去了每层新建、拷贝、销毁临时数组的往返操作。对大规模排序来说，内存分配次数从 O(nlogn) 级别的多次变成了 1 次，收益非常明显。

4.3 局部有序提前返回

归并排序对输入不敏感，但我们可以给它加一个敏感的判断：如果左右两个子数组合并之前就已经天然有序，那就不合并了。判断条件很简单，看左半区最后一个元素是否小于等于右半区第一个元素：

if (arr[mid] <= arr[mid + 1]) { return; }

如果成立，说明整个区间的最大值在左半区末尾，最小值在右半区开头，那左右两半拼起来已经整体有序，合并纯属浪费。这个优化在数据接近有序时效果极其明显，能让归并排序在“几乎有序”的数组上近乎线性地完成。虽然算法的最坏复杂度不变，但实际场景中它的平均表现会有实打实的提升。

要注意的是，这三个优化可以同时叠加，互不冲突。工程上这么实现的归并排序，无论是稳定性、内存分配还是实际耗时，都已经非常接近标准库排序的表现。

5. 绕不开的变体：自底向上、链表归并与外部排序

5.1 自底向上归并：递归栈深度可控

前面讲的都是递归版本，逻辑清晰但依赖系统调用栈。自底向上的非递归写法是另一条路线：不拆分，而是先让相邻的每 1 个元素为一组，两两归并，得到长度为 2 的有序块；再让相邻的每 2 个元素为一组，两两归并，得到长度为 4 的有序块；以此类推，直到整个数组有序。

function mergeSortBottomUp(arr) { const n = arr.length; const helper = new Array(n); for (let size = 1; size < n; size *= 2) { for (let left = 0; left < n - size; left += 2 * size) { const mid = left + size - 1; const right = Math.min(left + 2 * size - 1, n - 1); merge(arr, left, mid, right, helper); } } }

合并函数可以复用上一节的辅助数组版本。这个写法的好处是彻底摆脱递归深度限制，而且代码的执行路径非常直白。坏处是处理数组最后剩下那一截不完整块时，边界算起来要更小心，Math.min的钳位不能漏。

5.2 链表归并：空间复杂度可以做到 O(1)

数组归并需要 O(n) 的额外空间，是因为合并时需要临时存数据。但链表不是连续内存，合并两个有序链表只需要改指针，不需要任何额外数组。所以链表上的归并排序，额外空间只取决于递归栈深度，也就是 O(logn)，如果再用自底向上的方式，额外空间甚至可以压到 O(1)。

链表归并的思路是：用快慢指针找到链表的中点，快指针每次走两步，慢指针每次走一步，快指针到达末尾时慢指针正好在中点。然后递归地对前后两段分别排序，最后用标准的两个有序链表合并过程把它们串起来。合并两个有序链表时，谁的头节点小，谁就先进入结果链，然后更新对应指针。这个操作非常干净，也是因为链表天然适合“归并”这种线性操作。

5.3 外部排序：归并思想的工业级应用

归并排序最大的舞台其实不在内存里，而在磁盘上。

当数据量超过内存容量时，把所有数据一次性读进内存排序是不可能的。外部排序的做法是：把大文件切分成多个能够完整读入内存的小块，每个小块分别排序后写回磁盘，形成若干有序段；然后再把这些有序段做多路归并，逐一比较各段开头的元素，把最小的依次写入最终文件。整个过程的核心，就是归并排序的合并思路。

多路归并时，通常用堆来优化比较过程：从 K 个有序段中选出最小元素，不需要每轮比较 K 次，而是维护一个大小为 K 的最小堆，每次取出堆顶，再从所属的段中补入下一个元素，复杂度从 O(K) 降到 O(logK)。这个技术在数据库、搜索引擎、日志处理这些领域是真实每天都在跑的。你去面试后端方向，聊到海量数据排序，大概率会扯到这里。能说出“外部排序本质就是归并排序 + 堆优化”，面试官会知道你确实懂原理而不只是背代码。

6. 常见问题与排查技巧速查表

6.1 高频踩坑点对照表

6.2 实操心得：这样调试效率最高

写归并排序时，我最推荐的调试方式是“小数组手推”。拿[4, 3, 2, 1]这种 4 个元素的逆序数组，在纸上画递归树，把每一步的 left、mid、right 和 merge 后的数组状态写出来。跑一遍程序对比，基本半小时内就能把所有边界问题暴露完。

还有一个实用技巧：在 merge 开始时加一行日志，把left, mid, right和合并前的数组打出来，能快速定位到底是拆分错了还是合并顺序错了。工程里排查数据管道问题也是这个思路——先看输入再看出输，中间逻辑用日志锚定。

另外，面试时如果写归并排序，我建议先把思路口头说清楚，告诉面试官这是分治，先递归后合并，然后写一个 merge 函数和一个递归主函数，结构比直接堆代码要清楚得多。写完主动提一句“这里用<=是为了保持稳定性”，会显得你对细节有掌控力。别小看这些表现，它往往是面试官决定要不要深挖你的关键信号。

我个人在实际使用里的体会是，手写归并排序的机会虽然不多，但理解这套分治框架非常划算。它的“局部有序到整体有序”的思路，在合并接口返回的数据、整合多个有序列表、处理增量数据归并这些业务场景里都直接能用。把归并排序当成一个可以迁移的思维工具来看待，收获远大于“会背一个排序算法”。

最后再分享一个小技巧：如果你在实现时需要临时验证排序是否正确，不要只测随机数组，务必测一下全部相等的[5,5,5,5,5]和完全逆序的[5,4,3,2,1]。前者能测出稳定性写没写对，后者能测出递归边界和合并逻辑是否坚固。这两个用例过了，归并排序基本就算写得扎实了。