归并排序详解：算法原理、复杂度分析、代码实现与典型应用

归并排序Merge Sort也叫合并排序是数据结构与算法课程里绕不开的经典排序。它的核心是二路归并——把两个已经有序的子序列合并成一个新的有序序列。听起来不复杂但真正动手写一遍你会发现里面藏着不少细节递归边界、临时数组的管理、中间位置的取法、稳定性条件的判断每一个都是坑。这篇博文我打算围绕二路归并排序把它的算法原理、复杂度推导、代码实现、典型应用和常见错误完整地过一遍。无论你是正在准备考研数据结构、刷LeetCode的求职者还是刚学完冒泡排序和选择排序、想啃下更硬核算法的初学者这篇文章都能帮你把归并排序从听说过变成写得对。我会用我实际写代码的经验来讲哪里容易错、为什么这样写更稳都会说清楚。1. 算法思路拆解核心概念与设计思路1.1 分治思想的落地二路归并排序是分治策略的典型代表。所谓分治就是分而治之——把一个大问题拆成若干个小问题小问题解决了再合并起来解决大问题。这个思路在归并排序里表现得非常直白。假设你要给一个长度为 n 的数组排序。归并排序会这样干把数组从中间切成两半。对左半边递归地执行归并排序。对右半边递归地执行归并排序。把两个已经各自有序的半边合并成一个完整有序的数组。前三步是分最后一步是治。每次递归都把规模除以 2直到子数组只含一个元素——一个元素天然就是有序的不需要再排序。然后从底向上每次合并两个有序子数组最终整个数组有序。理解这个思路关键是抓住一个点merge合并是归并排序的主角。递归只是负责把一个数组拆到足够小而真正让数据变有序的是那一次次把两个有序数列合并的操作。很多初学者总盯着递归觉得递归难懂其实把 merge 想明白了整个算法就通透了一半。我习惯用一个类比来理解 merge你手里有两叠已经从小到大排好的扑克牌现在要把它们合成一叠依然有序的牌。你只需要每次比较两叠牌顶上的那一张谁小就先拿走谁放到结果堆里。如果某叠空了就把另一叠剩下的直接接上去。归并排序的 merge 过程本质就是这个扑克牌动作的代码化。1.2 相邻有序子序列的合并逻辑merge 操作的具体场景永远是两个相邻的有序区间。为什么必须相邻因为归并排序的操作对象是同一个数组左边的子区间是 [left, mid]右边的子区间是 [mid1, right]它们紧挨着。合并后要写回的位置就是原来的 [left, right] 区间。合并时的核心操作如下用三个下标 i、j、k分别指向左子序列的头部、右子序列的头部、临时数组的写入位置。循环比较 arr[i] 和 arr[j]谁小就把谁放到临时数组然后对应指针后移。当其中一个子序列被取完直接把另一个子序列剩余的元素全部复制过去。最后把临时数组里 [left, right] 区间的数据覆盖回原数组。这里有一个很关键的设计决策为什么要引入临时数组也叫辅助数组因为如果直接在原数组里交换元素会破坏还没有参与比较的元素导致数据丢失或覆盖。归并排序需要额外的空间来暂存中间结果这是它的空间复杂度是 O(n) 的原因。后面我会专门展开讲复杂度这里先说结论临时数组是归并排序正确性的基石不能省。另外一个细节是合并时比较条件我习惯写成arr[i] arr[j]而不是arr[i] arr[j]。这个等号的差别直接影响排序的稳定性。取等号时当两个元素值相等我们优先取左子序列的元素保持了它们在原数组中的相对顺序所以归并排序是稳定的写反了稳定性就会悄悄丢。这部分在代码实现章节我会再强调一次。2. 复杂度分析与稳定性论证2.1 时间复杂度的两种推导方法很多教材直接告诉你归并排序的时间复杂度是 O(nlogn)但为什么才是真正值得搞懂的地方。我有两种推导方法第二种尤其适合考试和面试时快速口头论证。第一种方法写递推式。设 T(n) 表示对 n 个元素排序的时间。归并排序把问题拆成两个规模为 n/2 的子问题分别需要 T(n/2) 的时间再加上一次合并所需的时间 O(n)。于是T(n) 2T(n/2) O(n)T(1) O(1)用主定理Master Theorem求解a2b2f(n)O(n)log_b(a)log_2(2)1f(n) 与 n^log_b(a) 同阶。主定理第二种情况直接给出 T(n)O(nlogn)。第二种方法递归树法也适合画图理解。把 T(n) 2T(n/2) O(n) 展开成递归树每一层所有子问题的规模加起来都是 n而整棵树的高度是 log₂n。每层合并的总代价都是 O(n)所以总代价是 O(nlogn)。我更推荐第二种方法因为它直观而且面试时画一张递归树比念主定理公式更有说服力。值得注意的是归并排序的时间复杂度无论数据本来是什么顺序永远是 O(nlogn)。这是它最大的优点也是它与快速排序拉开的差距——快排的 worst case 是 O(n²)而归并排序没有这种运气好与坏的差别。2.2 空间复杂度为什么是 O(n)空间复杂度 O(n) 的来源就是之前提到的临时数组。每次 merge 前我们需要申请一个长度为 n 的辅助数组来暂存合并结果或者在整个排序开始时一次性申请一个同样长度的数组反复使用。这里有一个区分有的教材把归并排序的空间复杂度写成 O(n)有的写成 O(nlogn)。问题出在每次递归都各自申请临时数组这种写法上。如果你在递归函数内部malloc一个临时数组那么递归树每一层都会申请数组总申请量会叠加到 O(nlogn)。但实际应用中我们不会这么干——更专业的做法是在最外层一次性申请一个长度 n 的临时数组所有递归层共享它这样实际占用空间就是 O(n)。如果再加上递归调用栈的高度 O(logn)严格说空间复杂度是 O(nlogn)但 logn 作为低阶项会被忽略所以结论就是 O(n)。我见过不少人面试时被问到归并排序的空间复杂度回答 O(nlogn)然后被追问为什么。其实就是没搞清楚临时数组是反复使用还是每层各自申请。面试答题时先说清一次性申请、复用临时数组空间复杂度是 O(n)这样不容易被挑毛病。2.3 稳定性归并排序最容易被问到的特性稳定性是排序算法的一个评价维度如果有两个相等元素排序后它们的相对位置不变就称这个算法是稳定的。归并排序是一个稳定排序这一点在面试和考试中经常被单独拿出来问。稳定性的实现其实只在 merge 里的一行代码if (arr[i] arr[j])时取左子序列的元素。当左右两个元素相等时我们让左边的先走这样右边的等值元素自然排到了后面相对顺序没有被破坏。与之形成对比的是快速排序和堆排序它们通常是不稳定的排序。快排的 partition 过程会把元素跨越式地交换位置相等元素的相对顺序很难保证堆排序的堆化过程同样会打乱相等元素的位置。所以当业务场景要求按多字段排序且保持第一个字段相同元素的原始顺序时稳定排序就有了不可替代的价值。3. 从零手写代码实现与实操要点3.1 递归版本自顶向下递归版本的实现逻辑最贴合分治思想也是教材里最常见的写法。我用 C 语言写一个完整版本重点在 merge 函数。#include stdio.h #include stdlib.h // 合并 [left, mid] 和 [mid1, right] 两个有序区间 void merge(int arr[], int tmp[], int left, int mid, int right) { int i left; // 左子序列起点 int j mid 1; // 右子序列起点 int k left; // 临时数组写入位置 // 两边都没取完时谁小取谁 while (i mid j right) { if (arr[i] arr[j]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } // 左子序列剩余元素直接复制 while (i mid) { tmp[k] arr[i]; } // 右子序列剩余元素直接复制 while (j right) { tmp[k] arr[j]; } // 把合并结果写回原数组 for (int idx left; idx right; idx) { arr[idx] tmp[idx]; } } // 递归入口 void merge_sort_recursive(int arr[], int tmp[], int left, int right) { if (left right) return; // 递归基区间内只有一个或没有元素 int mid left (right - left) / 2; // 防溢出写法 merge_sort_recursive(arr, tmp, left, mid); merge_sort_recursive(arr, tmp, mid 1, right); merge(arr, tmp, left, mid, right); } // 对外的封装函数 void merge_sort(int arr[], int n) { int *tmp (int *)malloc(n * sizeof(int)); if (tmp NULL) return; merge_sort_recursive(arr, tmp, 0, n - 1); free(tmp); }两处细节我想专门说明。第一处是mid left (right - left) / 2而不是(left right) / 2。当数组很大时left right 可能超过 int 的表示范围导致溢出虽然普通课程设计里几乎不可能触发但这是面试官喜欢考察的边界细节。第二处是临时数组的处理我在 merge_sort 外部分配好 tmp传给递归函数复用。这是我在做排序算法对比实验时养成的习惯后来发现这个习惯能省掉大量不必要的 malloc 和 free——递归深度一深反复申请内存的性能损失非常明显。笔试时如果限制你用固定空间或者你不确定平台的内存管理能力一次性分配临时数组也更安心。3.2 迭代版本自底向上递归虽然好理解但面试官喜欢追问的另一步是不用递归你怎么写归并排序这就需要掌握自底向上的迭代实现。迭代版的思路是从数组的每个元素各自有序开始先两两合并成若干个长度为 2 的有序块再合并成长度为 4 的有序块以此类推直到整个数组合并完成。用变量 width 表示当前有序块的宽度不断翻倍即可。void merge_sort_iterative(int arr[], int n) { if (n 1) return; int *tmp (int *)malloc(n * sizeof(int)); if (tmp NULL) return; for (int width 1; width n; width * 2) { for (int left 0; left n; left 2 * width) { int mid left width - 1; if (mid n) break; // 右边没有元素跳过合并 int right left 2 * width - 1; if (right n) right n - 1; // 右边界收窄到数组尾部 merge(arr, tmp, left, mid, right); } } free(tmp); }这里的关键判断是mid n的情况。当某一轮遍历中左边块开始位置 left 加 width 减 1 已经超出数组范围说明这个区域内没有两个完整的子序列可以合并直接跳过。另一个细节是 right 可能超过 n-1必须截断。迭代版的时间复杂度和递归版一致都是 O(nlogn)。它的好处是不用担心递归深度数据量特别大时可以避免栈溢出。我在项目里如果要手写归并排序通常会优先用迭代版因为可控性更强。3.3 手写时的三个关键细节第一个细节是递归基。if (left right) return;这行不能写成if (left right) return;虽然它也能工作但一旦因为某种原因区间被传成 left right比如 mid 计算错误或边界判断失误就会陷入无限递归最后栈溢出。用是一个防御性写法成本为零收益很大。第二个细节是写回。我第一次实现时把 merge 里写回原数组的 for 循环漏掉了测试时发现数组前一半有序后一半全是垃圾数据。临时数组只是暂存最终结果必须覆盖回原数组这个动作必须放在 merge 函数内且要覆盖整个 [left, right] 区间只写回一部分也会出问题。第三个细节是复杂度分析时的隐藏常量。归并排序虽然时间复杂度同为 O(nlogn)但它的常量因子比快速排序大因为需要额外的数组拷贝。实际工程里当数据规模较小比如 n 小于 64时很多实现会切换到插入排序来提速。我本人在做性能对比实验时也验证过这个优化阈值设在 32~64 之间归并排序整体耗时能降低 10%~20%。这个优化不算复杂但能体现你对算法细节的理解面试里主动提出来是加分项。4. 归并排序的进阶应用4.1 外部排序内存装不下时怎么办归并排序最经典的应用场景是外部排序——当待排序数据量大到无法一次性加载进内存时基于内存的排序算法全都无能为力而归并排序的思路却能天然扩展出去。典型的外部排序流程是把大文件切分成多段每段都能完整读入内存对每一段用内部排序通常用快排或归并排序排好写回磁盘形成多个有序的临时文件最后用归并排序的思路把这些有序临时文件进行多路归并最终生成整个文件的有序版本。这里的多路就是二路归并的推广——每次从 k 个文件中各取一个最小元素比较后挑出最小的写回结果文件。我自己在课程设计里处理过几个 GB 的日志文件用到的工具底层就是外部归并排序。当时最大的体会是IO 次数决定了外部排序的性能。二路归并需要 log₂n 轮磁盘读写而 k 路归并能把轮数降到 log_k(n)所以工程化的外部排序通常会配合败者树优化 k 路归并的选择过程。虽然考试一般只要求能画出分块排序 归并的示意图但知道这层背景有助于你真正理解归并排序为什么被誉为最工程化的排序算法。4.2 链表排序的归并思路归并排序在链表上的应用是 LeetCode 高频题148. 排序链表。数组的归并排序需要 O(n) 的辅助空间而链表版本可以做到 O(1) 额外空间不算递归栈因为链表节点的合并只是调整指针指向不需要搬动数据。链表归并的思路和数组几乎一样但实现上有几个差异点找中点数组用下标计算链表用快慢指针快指针一次走两步慢指针一次走一步快指针走到尾时慢指针恰好在中间。切断链表在 mid 处把链表分成两条独立的子链表否则递归划分时无法正确终止。merge 时不能用临时数组而是比较两个链表的头节点值用尾插法把较小的节点串起来。这个题目我每次刷都能发现新的问题最常见的坑是递归划分后没有把 left 链表的尾节点 next 置空导致合并时出现环。如果你正在刷题我建议把链表归并和数组归并放在一起练对比着写对分治思想的理解会非常深刻。4.3 归并排序与其它排序的选型取舍把归并排序与快速排序、堆排序放在一起看是理解排序算法全貌的最快路径。我用一张表总结它们的核心差异排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性特点与适用场景二路归并排序O(nlogn)O(nlogn)O(n)稳定链表排序、外部排序、需要稳定性的场景快速排序O(nlogn)O(n²)O(logn)不稳定通用数组排序工程中常量小实测最快堆排序O(nlogn)O(nlogn)O(1)不稳定需要原地排序、空间受限的场景冒泡排序O(n²)O(n²)O(1)稳定教学用数据量小时可用插入排序O(n²)O(n²)O(1)稳定近乎有序的数据效率极高我用这张表是想强调一个观点没有最好的排序只有最合适的排序。快排综合性能强但它最坏情况下会退化。堆排序空间最省但节点跳跃式访问对缓存不友好实际运行不一定快过归并。归并排序稳定、性能有保证就是空间消耗大。在实际工程里Java 的Collections.sort就是为对象排序设计成归并排序变体的因为对象比较可能开销大稳定性重要而且对象在堆中本来就分散额外拷贝对象的引用比拷贝大对象本身便宜得多C 的std::stable_sort也是归并排序的思路。这些事实都说明归并排序不是理论上的空架子而是被真实工程反复验证过的可靠方案。5. 常见错误与避坑指南5.1 高频Bug速查表我在指导学弟学妹写归并排序时反复遇到的错误几乎可以总结成一张速查表。如果你写完代码测试不通过优先按这张表排查错误类型典型表现根本原因修复方法忘写回原数组前部分有序后部分乱merge 最后没有把 tmp 拷回 arr在 merge 末尾加一个 for 循环写回递归基写错栈溢出left right 无法覆盖空区间改为 left right下标越界数组越界或读到垃圾值mid/right 计算错误或边界判断用错仔细检查每个区间的开闭建议用 left (right-left)/2比较条件写反排序结果不稳定arr[i] arr[j] 导致等值元素互换改成 arr[i] arr[j]每层新建临时数组内存碎片、性能极差在 merge 内部反复 malloc外层一次性申请递归复用一个 tmp迭代版 mid 判断缺失偶发乱序mid n 时未跳过合并加if (mid n) break;防御这些坑我几乎全踩过一遍。最让我记忆犹新的是考研备考时我手写迭代版归并排序把 right 的截断和 mid 的跳跃判断搞反了导致最后一轮合并时把已经有序的左右两段错误地合并成乱序。当时调试了很久才发现是 width 循环边界的问题。所以我的建议是写完代码先拿小数组跑一遍打印每一轮合并后的数组确认每个 width 的合并结果这个过程能帮你快速定位边界错误。5.2 面试与考试中的高频考点归并排序在笔试面试中的出镜率极高考察形式也很固定。我把常见的考点整理了一下手写递归版归并排序是几乎所有算法岗位的入门关。问时间复杂度、空间复杂度的推导要求你解释 O(nlogn) 的来源。问稳定性并举例说明为什么归并排序能保持稳定。问迭代版怎么写考察你是否理解自底向上的过程。问如何用归并排序解决 logn 时间内的求逆序对问题。问归并排序与快排的区别以及什么时候该用归并排序。求逆序对这个问题值得单独说一句。在一个数组里如果 i j 且 arr[i] arr[j]就构成一个逆序对。归并排序在合并左右两个有序子序列时每当右边元素 arr[j] 小于左边的 arr[i]说明左子序列中从 i 到 mid 的所有元素都比 arr[j] 大这时就可以一口气统计出 (mid - i 1) 个逆序对。这个技巧把原本 O(n²) 的暴力统计降到了 O(nlogn)属于归并排序最漂亮的进阶应用。很多考研数据结构的填空题和编程题都会考到这个知识点。5.3 性能优化心得归并排序的基础实现已经很稳定但如果追求更极致的性能有几个优化手法值得尝试。第一个是小区间使用插入排序当待排序区间长度小于某个阈值比如 16 或 32时直接调用插入排序减少递归调用的开销。第二个是在 merge 之前加一个判断如果左子序列的最后一个元素已经小于等于右子序列的第一个元素说明两个子序列合并后本来就是有序的可以跳过这次合并。这个剪枝对近乎有序的数据效果显著。第三个优化是关于临时数组的复用。每次 merge 都完整地拷贝一遍区间其实可以交替使用两个数组来减少拷贝次数甚至用原地归并的算法来省掉临时数组。但原地归并的实现复杂度很高运行效率也未必好实际工程里很少用。我个人的建议是基础掌握好了再做这些优化不要在刚开始学的时候就陷入这些炫技细节先把基础的递归版写对、写稳再慢慢加花样。数据量的影响也值得一说。当 n 比较小几百以内时各个排序算法的差异并不明显甚至插入排序可能因为简单的循环操作而比归并排序更快。当 n 到十万、百万级别归并排序的 O(nlogn) 优势会明显体现出来。我自己做过一次简单的性能对比随机生成 100 万个整数归并排序大约需要 0.3 秒左右视机器和编译器而定冒泡排序在这个数据量下根本不现实。排序算法的选型必须结合数据规模和实际硬件环境来考虑不能只背复杂度结论。最后分享一个我个人的亲身体会。有一次我在处理链表排序时因为递归实现总是出现链表环一度怀疑是合并逻辑写错了。后来把中间打印出来才发现问题出在划分时没有切断链表。这种问题单靠眼睛盯着代码很难发现但如果你理解归并排序的本质是先拆、后合就会知道拆的时候必须要彻底拆开才算完成第一步。这个小小教训让我每次写归并排序的代码都会下意识检查分这一步有没有真正把数据分成两个独立部分。希望对你有同样的帮助。