尧图网站建设 
归并排序Merge Sort在 CSDN 上常被贴上“稳定、高效、但空间复杂度高”的标签。很多初学者看完这个概念拿起代码一看就懵明明排序为什么要递归拆分为什么合并时要开临时数组动画里“分——治——合”很流畅自己动手写却总是数组越界或者死递归。这篇文章想解决的问题很明确让零基础读者用大约 2 小时彻底搞懂 C 语言归并排序的过程并且能自己手写出一份没有 bug 的归并排序代码。我会用一个 7 个元素的数组走完整轮图示把“递归”的调用过程翻出来看再给出完整可复制的 C 语言代码最后分析时间复杂度和易错点。这部分内容也适合准备计算机二级、考研数据结构或者刷 LeetCode 前补排序基础的读者。我的判断是归并排序不是最难写的排序算法但它是第一个值得反复咀嚼的排序算法。因为它要求你同时理解“分治”和“递归”两个抽象概念。一旦掌握再看快速排序、堆排序思维层次会完全不一样。1. 这篇文章真正要解决的问题很多初学者对归并排序的困惑不在于“合并两个有序数组”这一步而在于**“为什么排序问题需要递归地把自己拆成两半”**。最常见的挫败感有三个来源代码能看懂但过程想不明白。函数里套函数一层层分下去最后又一层层合并回来大脑的“调用栈”不够用了。合并逻辑写不完整。新手容易只写一个 while 循环把一个数组搬完就结束结果漏掉了另一半。边界条件控制不好。left、mid、right三个下标差一个数数组就越界程序直接崩溃。所以这篇文章不只是贴一段归并排序代码。我会按下面的顺序来组织先讲分治思想把“递归拆分 合并”用生活场景翻译一遍。再用图示走一遍完整排序过程模拟动画的每一帧。然后给出在 C 语言环境里可以直接编译运行的完整代码。最后拆解递归调用栈分析复杂度并列出常见 bug 的排查方法。学完这篇文章你应该能收获三点第一能徒手写出 merge 函数和 mergeSort 函数第二能说清楚每一行代码在执行时到底在做什么第三遇到“为什么不用快速排序代替归并排序”这类面试问题能给出有深度的回答。2. 归并排序的核心思想分治归并排序的核心是一种叫“分治Divide and Conquer”的算法策略。所谓分治就是把一个复杂问题拆成若干个规模较小、结构相同的子问题分别解决最后把子问题的结果合并成最终答案。2.1 先看一个生活场景假设你要把一整层书架上的书整理得按书名有序。你的办公桌不够大一次只能处理两本书。怎么办聪明的方法不是站在书架前反复抽插书而是把书架上的书平均分成两堆如果一堆里的书还是太多就继续分直到每堆只剩一本书——只有一本书时它天然是有序的然后从最小的堆开始两两合并每次比较两堆最前面的书把书名靠前的书放入新位置合并后的堆越来越大最后整层书架都有序了。这个过程就是归并排序的完整缩影。“分”是递归向下拆的过程“治”是递归回溯时合并的过程。2.2 归并排序的三大步骤用技术语言描述归并排序对数组arr[left]到arr[right]排序时只需要做三件事分解Divide计算中间位置mid (left right) / 2把数组分成左半区间[left, mid]和右半区间[mid1, right]。解决Conquer递归地对左半区间调用归并排序再递归地对右半区间调用归并排序。递归终止条件是区间里只剩一个元素或为空。合并Merge把已经有序的左右两个区间合并成一个更大的有序区间。代码层面归并排序只需要两个核心函数merge合并两个有序区间这是整个算法的关键。mergeSort递归拆分区间然后调用 merge 完成合并。2.3 为什么归并排序需要额外空间和冒泡排序、选择排序这种“在原数组上交换”的排序算法不同归并排序不是通过交换来排序的而是通过**“把两个有序序列归并成一个有序序列”**来排序。合并两个有序序列时如果完全在同一个数组上原地操作最坏情况下需要大量搬移元素时间复杂度会退化。为此归并排序通常申请一个临时数组把要合并的元素缓存进去再写回原数组。这就是它空间复杂度为 O(n) 的原因。这也是归并排序最大的特点和争议点它用 O(n) 的额外空间换来了稳定的 O(n log n) 时间复杂度和排序稳定性。3. 图解归并排序全过程文字描述再准确也不如一步步走完一个数组来的实在。下面用数组arr [38, 27, 43, 3, 9, 82, 10]来演示归并排序的全过程。建议你把下面这段当成“动画的每一帧”来看。3.1 分解阶段递归向下整体区间是[0, 6]mid 3拆成左[38, 27, 43, 3] 右[9, 82, 10]继续分解左半区[0, 3]mid 1拆成左[38, 27] 右[43, 3]继续拆[38, 27]mid 0拆成左[38] 右[27]此时左右都只剩一个元素递归到达终点。同理右侧的所有区间也会被分解到单元素。分解结束后整个数组在逻辑上变成了 7 个“单元素子数组”[38] [27] [43] [3] [9] [82] [10]每一个单元素区间天然有序等待合并。3.2 合并阶段递归回溯现在开始两两合并第一步合并[38]和[27]比较 38 和 2727 更小先放入再放 38。 结果[27, 38]第二步合并[43]和[3]结果[3, 43]第三步合并[27, 38]和[3, 43]比较过程 27 vs 33 小取 3 27 vs 4327 小取 27 38 vs 4338 小取 38 最后放 43。 结果[3, 27, 38, 43]至此原数组的左半区已经有序。右半区同理[9] [82] [10] → 合并 [9] 和 [82]得到 [9, 82] → 合并 [9, 82] 和 [10]比较过程 9 vs 10取 9 82 vs 10取 10 最后放 82。 结果[9, 10, 82]最后合并左半区[3, 27, 38, 43]和右半区[9, 10, 82]比较过程这里最能体现归并排序的精髓两个指针分别扫描两个数组 3 vs 9 → 取 3 27 vs 9 → 取 9 27 vs 10 → 取 10 27 vs 82 → 取 27 38 vs 82 → 取 38 43 vs 82 → 取 43 剩余82 → 取 82 最终结果[3, 9, 10, 27, 38, 43, 82]整个排序完成。你可以看到每一次 merge 操作都是在处理两个“已经有序”的区间这是归并排序能够高效工作的大前提。4. C语言完整实现归并排序下面给出可编译运行的完整 C 语言代码。代码包含三部分merge函数、mergeSort函数和主函数测试。建议你在自己的编译器里新建一个.c文件把代码粘贴进去运行。// 文件路径merge_sort_demo.c #include stdio.h #include stdlib.h // 打印数组方便观察排序前后结果 void printArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } printf(\n); } // 合并两个有序区间 // 左半区间 [left, mid] // 右半区间 [mid1, right] void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; // 左半区间元素个数 int n2 right - mid; // 右半区间元素个数 // 申请临时数组保存左右区间的数据 int *L (int*)malloc(n1 * sizeof(int)); int *R (int*)malloc(n2 * sizeof(int)); if (L NULL || R NULL) { printf(内存分配失败\n); exit(1); } // 拷贝数据到临时数组 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]; } // 合并两个有序数组到 arr[left..right] int i 0; // L 的遍历下标 int j 0; // R 的遍历下标 int k left; // 原数组的写入位置 while (i n1 j n2) { // 注意使用 保证排序稳定性 if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } // 如果 L 中还有剩余元素直接拷贝到 arr while (i n1) { arr[k] L[i]; i; k; } // 如果 R 中还有剩余元素直接拷贝到 arr while (j n2) { arr[k] R[j]; j; k; } // 释放临时数组 free(L); free(R); } // 归并排序主函数 // arr待排序数组 // left排序区间左边界下标 // right排序区间右边界下标 void mergeSort(int arr[], int left, int right) { // 递归终止条件区间内只有一个元素或没有元素 if (left right) { return; } // 计算中间位置防止 (leftright) 溢出写成 left (right-left)/2 int mid left (right - left) / 2; // 递归排序左半区间 mergeSort(arr, left, mid); // 递归排序右半区间 mergeSort(arr, mid 1, right); // 合并两个有序区间 merge(arr, left, mid, right); } int main() { int arr[] {38, 27, 43, 3, 9, 82, 10}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); mergeSort(arr, 0, n - 1); printf(排序后); printArray(arr, n); return 0; }这段代码有几个细节值得单独说明。第一mid的计算用了left (right - left) / 2而不是(left right) / 2。后者在left right特别大时可能整型溢出前者可以规避这个边界问题。这是一个非常好的编程习惯在 LeetCode 题解里也经常能看到。第二merge 函数里两个while循环负责处理“剩余元素”。因为两个临时数组的长度不一定相同合并后必然有一个数组会先被取空另一个还有剩余。直接循环拷贝剩余元素即可。第三比较时用的是而不是。当L[i]等于R[j]时优先取左半边的元素。这是归并排序稳定性的关键来源。5. 运行验证与过程追踪编译运行上面的代码输出如下排序前38 27 43 3 9 82 10 排序后3 9 10 27 38 43 82如果结果和这段输出不一样优先检查 merge 函数里的下标逻辑。为了方便调试你可以在 merge 函数开始时打印当前要合并的区间printf(合并区间 [%d, %d] 和 [%d, %d]\n, left, mid, mid1, right);这样程序运行时会输出类似下面的信息合并区间 [0, 0] 和 [1, 1] 合并区间 [2, 2] 和 [3, 3] 合并区间 [0, 1] 和 [2, 3] 合并区间 [4, 4] 和 [5, 5] 合并区间 [4, 5] 和 [6, 6] 合并区间 [0, 3] 和 [4, 6]从这组输出你可以清晰地看到递归的执行顺序先完全处理左半区再处理右半区最后合并整个区间。5.1 用调试器观察递归调用栈如果你使用 VS Code GCC、Visual Studio 或者 CLion 等 IDE可以在mergeSort函数的if (left right)那一行打断点观察递归调用栈。你会看到第一次调用mergeSort(arr, 0, 6)进入后调用mergeSort(arr, 0, 3)再调用mergeSort(arr, 0, 1)再调用mergeSort(arr, 0, 0)此时触发left right直接返回然后回到上一层调用mergeSort(arr, 1, 1)返回再执行 merge合并[0, 0]和[1, 1]。这个“先深入左子树再处理右子树最后合并”的模式和二叉树的后序遍历非常相似。如果你学过树的遍历会发现归并排序的递归结构天然形成一棵递归树。6. 复杂度分析为什么归并排序性能稳定6.1 时间复杂度设归并排序处理 n 个元素的时间为 T(n)。一次归并排序可以写成递推式T(n) 2 * T(n/2) O(n)其中2 * T(n/2)是递归处理左右两个半区的时间O(n)是一次合并的时间。用主定理Master Theorem或者逐层展开推导T(n) 2T(n/2) O(n) 2(2T(n/4) O(n/2)) O(n) 4T(n/4) 2O(n) 8T(n/8) 3O(n) ... n * T(1) log2(n) * O(n) O(n log n)也就是说归并排序的时间复杂度是O(n log n)无论输入数据是正序、逆序还是乱序这个复杂度都成立。这一点和快速排序不同——快速排序在最坏情况下比如每次选的基准值都是最大值或最小值会退化到 O(n²)而归并排序没有这个缺陷。6.2 空间复杂度归并排序的空间复杂度是 O(n)因为它每次 merge 时都会分配临时数组。如果把递归调用栈的开销也算进去空间复杂度就是 O(n log n)但通常我们简化为 O(n)。相比之下排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定从表格可以看到归并排序的核心优势是无论什么情况它都能保持 O(n log n) 的时间复杂度并且保证稳定性。这个特性让它特别适合两类场景对稳定性有要求的排序。比如成绩排序总分相同的人希望按学号排序稳定排序能保证第一轮的相对顺序在第二轮不会被破坏。外部排序的基石。当数据量太大、内存放不下时可以把大文件拆成多个小块分别排序后再用归并的思路把多个有序文件合并成一个有序文件。6.3 为什么不总是用归并排序归并排序虽然稳定且复杂度优秀但它有一个硬伤额外内存开销 O(n)。在嵌入式开发、单片机编程或者内存极其受限的场景里O(n) 的额外空间是很大的负担。这时开发者会更倾向于“原地”排序的快速排序或堆排序。另一个原因是缓存局部性。归并排序需要频繁地把数据拷贝到临时数组再写回而快速排序是在原数组上交换元素对 CPU 缓存的利用更友好。所以在实际工程中很多排序库默认采用的是快速排序或优化过的混合排序而不是归并排序。但归并排序在“大数据量外部排序”和“需要稳定排序”的场合仍是不可替代的存在。7. 递归过程拆解代码到底是怎么执行的为了彻底解决“看得懂代码、想不通过程”的问题这里手动展开一次递归调用。以mergeSort(arr, 0, 6)为例mergeSort(arr, 0, 6) ├── mid 3 ├── mergeSort(arr, 0, 3) │ ├── mid 1 │ ├── mergeSort(arr, 0, 1) │ │ ├── mid 0 │ │ ├── mergeSort(arr, 0, 0) → 直接返回 │ │ ├── mergeSort(arr, 1, 1) → 直接返回 │ │ └── merge(arr, 0, 0, 1) → 合并 [38] 和 [27]得到 [27, 38] │ ├── mergeSort(arr, 2, 3) │ │ ├── mid 2 │ │ ├── mergeSort(arr, 2, 2) → 直接返回 │ │ ├── mergeSort(arr, 3, 3) → 直接返回 │ │ └── merge(arr, 2, 2, 3) → 合并 [43] 和 [3]得到 [3, 43] │ └── merge(arr, 0, 1, 3) → 合并 [27, 38] 和 [3, 43]得到 [3, 27, 38, 43] ├── mergeSort(arr, 4, 6) │ ├── mid 5 │ ├── mergeSort(arr, 4, 5) │ │ ├── mid 4 │ │ ├── mergeSort(arr, 4, 4) → 直接返回 │ │ ├── mergeSort(arr, 5, 5) → 直接返回 │ │ └── merge(arr, 4, 4, 5) → 合并 [9] 和 [82]得到 [9, 82] │ ├── mergeSort(arr, 6, 6) → 直接返回 │ └── merge(arr, 4, 5, 6) → 合并 [9, 82] 和 [10]得到 [9, 10, 82] └── merge(arr, 0, 3, 6) → 合并 [3, 27, 38, 43] 和 [9, 10, 82]得到最终有序数组仔细看这幅展开图你会发现一个规律mergeSort 的顺序是固定的“左 → 右 → 合并”。它先把整个问题一分为二对左边部分完全处理完之后再处理右边最后两边合并。为什么递归最后能正确工作因为每次 merge 的前提是“左右两个区间已经各自有序”。这个前提由递归调用保证递归进入时先把区间拆到只剩一个元素一个元素天然有序再一层层合并回去每次合并后的区间都是有序的。这就是所谓的“数学归纳法式的正确性”。8. 常见问题与排查思路下面是初学者写归并排序时最常踩的坑我整理成了表格方便你对照排查。问题现象可能原因排查方式解决方案程序崩溃提示数组越界merge 函数里 left、mid、right 边界计算错误打印每次 merge 的区间边界检查n1 mid - left 1和n2 right - mid是否算对区间为闭区间[left, right]计算长度时左闭右闭要 1递归无法终止栈溢出递归终止条件写错比如只写了left right检查是否存在left right的情况统一使用if (left right) return;排序结果错误但无崩溃merge 中漏掉了某个剩余数组的拷贝循环手动模拟一个 3 元素数组的合并过程必须包含两个 while 循环分别处理 L 和 R 的剩余元素内存分配失败导致异常临时数组 malloc 后没有判断返回 NULL增加判空逻辑并输出错误信息生产代码中if (L NULL || R NULL) exit(1);结果正确但排序不稳定合并时用了而不是用相同元素构造测试用例如[2, 1, 2]相等时先取左区间元素使用Visual Studio 提示 scanf 不安全使用了scanf相关函数VS 强制要求安全版本确认是否非要用 scanf学习阶段可用scanf_s注意参数格式不同其中最隐蔽的是“合并时漏拷贝剩余元素”。新手容易写完while (i n1 j n2)的循环后就直接结束函数结果发现数组中有一块区域的值没有写回原数组。这个 bug 在数组长度为偶数时不容易暴露一旦数组长度是奇数就会出现莫名的 0 或垃圾值。建议平时测试时多用奇数长度的数组。另一个高频错误是“修改了原数组但没有同步修改 mid”。比如有人图省事在mergeSort里直接写int mid (left right) / 2;这没有问题但如果在递归调用时把right写成mid就把右半区间漏掉了导致右侧元素永远排不到序。9. 归并排序与快速排序的对比谁才是更优解既然题目热搜词里包含了“快速排序 c 语言”这里专门做一次对比。学归并排序时很多人会问快速排序平均也是 O(n log n)而且原地排序、空间占用小为什么还要学归并排序这个问题的答案可以从三个层面看。第一稳定性。归并排序是稳定排序快速排序是不稳定排序。如果业务要求“先按分数排序分数相同的人保持原来的先后顺序”归并排序是天然合适的快速排序则做不到。第二最坏时间复杂度。快速排序在最坏情况下每次选取的基准都是极值时间复杂度是 O(n²)。虽然随机化基准可以降低这个概率但无法彻底消除。归并排序不存在这个问题它的 O(n log n) 是“无条件的”。第三递归结构。两者的递归结构非常不同。快速排序是“先分区再递归”的顺序归并排序是“先递归到底再合并”的顺序。理解归并排序的“后序合并”后再看快速排序的“前序分区”会更容易形成体系化认知。但在工程层面快速排序通常在大多数场景下更快。原因是它访问内存的模式更简单、缓存命中率更高不需要大量拷贝。归并排序的应用重心是外部排序和稳定性要求高的场景两者并不矛盾。10. 优化思路与扩展学习归并排序基础版本已经能够解决大部分问题但在工程中还有一些常见优化手段值得了解。10.1 小数组用插入排序递归到区间很小的时候比如数组长度小于 10 或 16可以不再继续递归而是改用插入排序。原因是插入排序在数组接近有序时表现很好而且没有递归调用和临时数组分配的开销。很多工业级的排序实现都会做这种“混合排序”优化。#define INSERTION_THRESHOLD 10 void mergeSortOptimized(int arr[], int left, int right) { if (right - left 1 INSERTION_THRESHOLD) { // 改用插入排序处理小数组 for (int i left 1; i right; i) { int key arr[i]; int j i - 1; while (j left arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } return; } int mid left (right - left) / 2; mergeSortOptimized(arr, left, mid); mergeSortOptimized(arr, mid 1, right); merge(arr, left, mid, right); }10.2 复用临时数组基础版本的 merge 每次排序时都 malloc 一块新内存频繁分配会影响性能。更常用的做法是在 mergeSort 外层只申请一次和原数组等大的临时数组然后把它作为参数传给 merge 函数。每次 merge 都使用同一块临时空间能显著减少运行时开销。10.3 归并排序的逆序对应用归并排序还有一个经典应用计算数组中的逆序对数量。在合并过程中如果左半边的某个元素大于右半边的某个元素那么左半边从当前位置到 mid 的所有元素都与右半边的这个元素构成逆序对。用这一思路可以在 O(n log n) 时间内完成统计面试中也很常考。11. 常见面试题与笔试高频考点归并排序是计算机二级、校招笔试和考研数据结构的热门考点。这里列几个最常见的追问读者可以自测是不是都能答得上来。归并排序是稳定的吗为什么是稳定的。因为合并时遇到相等元素会优先取左半区间的元素保持了原数组中的相对顺序。归并排序的空间复杂度是多少O(n)。额外空间主要来自合并时创建的临时数组。归并排序适合链表吗很适合。链表不适合快速排序的随机访问但归并排序只需要顺序访问用它给链表排序是很经典的实现。归并排序和快速排序的本质区别是什么归并排序的关键操作在“合并”递归发生在处理数据之前或之后没有本质区别快速排序的关键操作在“分区”数据移动发生在递归之前。归并排序时间稳定但空间大快速排序空间小但最坏情况可能退化。每次合并后数组一定有序吗是的。合并的前提是左右两个区间已经有序二路归并保证合并后的区间也是有序的。如果上面的问题都能顺利回答说明你对归并排序理解得已经足够扎实可以进入下一步手把手把归并排序改成链表版本或者尝试写一个不使用递归的归并排序。12. 给你的下一步建议从学习路径上看归并排序之后值得继续深入的内容有三个方向。先掌握概念的联系。归并排序、快速排序、堆排序都是“排序算法”这个主题下的分支但它们背后的策略不同。归并排序是“分治 递归合并”快速排序是“分治 原地分区”堆排序是“基于完全二叉树的选择排序”。把三者的代码和过程放在一起对比会比孤立的背诵效果好很多。然后动手刷题验证。力扣上有不少归并排序相关的题目比如排序数组、翻转对、计算右侧小于当前元素的个数。不需要刷很多两三道中等难度的题就足够检验你对“归并思想”的理解。最后接触真实场景。如果你的方向是后端开发或大数据找一份大数据量文件排序相关的开源代码看看外部排序如何利用归并思想。如果你做嵌入式开发可以思考如何用有限的 RAM 完成局部排序。技术只有落到场景里才算真正学会了。写归并排序的 C 语言代码本质上就是在练习两个能力递归地分解问题以及细致地处理边界条件。这两种能力是算法工程师和优秀开发者的基本功。建议你把代码复制下来多改几个数组长度多打印几次中间结果直到能不看参考代码独立写出为止。排序算法不需要背写多了自然就记住了。 C语言归并排序详解：分治递归与合并过程全图解
归并排序Merge Sort在 CSDN 上常被贴上“稳定、高效、但空间复杂度高”的标签。很多初学者看完这个概念拿起代码一看就懵明明排序为什么要递归拆分为什么合并时要开临时数组动画里“分——治——合”很流畅自己动手写却总是数组越界或者死递归。这篇文章想解决的问题很明确让零基础读者用大约 2 小时彻底搞懂 C 语言归并排序的过程并且能自己手写出一份没有 bug 的归并排序代码。我会用一个 7 个元素的数组走完整轮图示把“递归”的调用过程翻出来看再给出完整可复制的 C 语言代码最后分析时间复杂度和易错点。这部分内容也适合准备计算机二级、考研数据结构或者刷 LeetCode 前补排序基础的读者。我的判断是归并排序不是最难写的排序算法但它是第一个值得反复咀嚼的排序算法。因为它要求你同时理解“分治”和“递归”两个抽象概念。一旦掌握再看快速排序、堆排序思维层次会完全不一样。1. 这篇文章真正要解决的问题很多初学者对归并排序的困惑不在于“合并两个有序数组”这一步而在于**“为什么排序问题需要递归地把自己拆成两半”**。最常见的挫败感有三个来源代码能看懂但过程想不明白。函数里套函数一层层分下去最后又一层层合并回来大脑的“调用栈”不够用了。合并逻辑写不完整。新手容易只写一个 while 循环把一个数组搬完就结束结果漏掉了另一半。边界条件控制不好。left、mid、right三个下标差一个数数组就越界程序直接崩溃。所以这篇文章不只是贴一段归并排序代码。我会按下面的顺序来组织先讲分治思想把“递归拆分 合并”用生活场景翻译一遍。再用图示走一遍完整排序过程模拟动画的每一帧。然后给出在 C 语言环境里可以直接编译运行的完整代码。最后拆解递归调用栈分析复杂度并列出常见 bug 的排查方法。学完这篇文章你应该能收获三点第一能徒手写出 merge 函数和 mergeSort 函数第二能说清楚每一行代码在执行时到底在做什么第三遇到“为什么不用快速排序代替归并排序”这类面试问题能给出有深度的回答。2. 归并排序的核心思想分治归并排序的核心是一种叫“分治Divide and Conquer”的算法策略。所谓分治就是把一个复杂问题拆成若干个规模较小、结构相同的子问题分别解决最后把子问题的结果合并成最终答案。2.1 先看一个生活场景假设你要把一整层书架上的书整理得按书名有序。你的办公桌不够大一次只能处理两本书。怎么办聪明的方法不是站在书架前反复抽插书而是把书架上的书平均分成两堆如果一堆里的书还是太多就继续分直到每堆只剩一本书——只有一本书时它天然是有序的然后从最小的堆开始两两合并每次比较两堆最前面的书把书名靠前的书放入新位置合并后的堆越来越大最后整层书架都有序了。这个过程就是归并排序的完整缩影。“分”是递归向下拆的过程“治”是递归回溯时合并的过程。2.2 归并排序的三大步骤用技术语言描述归并排序对数组arr[left]到arr[right]排序时只需要做三件事分解Divide计算中间位置mid (left right) / 2把数组分成左半区间[left, mid]和右半区间[mid1, right]。解决Conquer递归地对左半区间调用归并排序再递归地对右半区间调用归并排序。递归终止条件是区间里只剩一个元素或为空。合并Merge把已经有序的左右两个区间合并成一个更大的有序区间。代码层面归并排序只需要两个核心函数merge合并两个有序区间这是整个算法的关键。mergeSort递归拆分区间然后调用 merge 完成合并。2.3 为什么归并排序需要额外空间和冒泡排序、选择排序这种“在原数组上交换”的排序算法不同归并排序不是通过交换来排序的而是通过**“把两个有序序列归并成一个有序序列”**来排序。合并两个有序序列时如果完全在同一个数组上原地操作最坏情况下需要大量搬移元素时间复杂度会退化。为此归并排序通常申请一个临时数组把要合并的元素缓存进去再写回原数组。这就是它空间复杂度为 O(n) 的原因。这也是归并排序最大的特点和争议点它用 O(n) 的额外空间换来了稳定的 O(n log n) 时间复杂度和排序稳定性。3. 图解归并排序全过程文字描述再准确也不如一步步走完一个数组来的实在。下面用数组arr [38, 27, 43, 3, 9, 82, 10]来演示归并排序的全过程。建议你把下面这段当成“动画的每一帧”来看。3.1 分解阶段递归向下整体区间是[0, 6]mid 3拆成左[38, 27, 43, 3] 右[9, 82, 10]继续分解左半区[0, 3]mid 1拆成左[38, 27] 右[43, 3]继续拆[38, 27]mid 0拆成左[38] 右[27]此时左右都只剩一个元素递归到达终点。同理右侧的所有区间也会被分解到单元素。分解结束后整个数组在逻辑上变成了 7 个“单元素子数组”[38] [27] [43] [3] [9] [82] [10]每一个单元素区间天然有序等待合并。3.2 合并阶段递归回溯现在开始两两合并第一步合并[38]和[27]比较 38 和 2727 更小先放入再放 38。 结果[27, 38]第二步合并[43]和[3]结果[3, 43]第三步合并[27, 38]和[3, 43]比较过程 27 vs 33 小取 3 27 vs 4327 小取 27 38 vs 4338 小取 38 最后放 43。 结果[3, 27, 38, 43]至此原数组的左半区已经有序。右半区同理[9] [82] [10] → 合并 [9] 和 [82]得到 [9, 82] → 合并 [9, 82] 和 [10]比较过程 9 vs 10取 9 82 vs 10取 10 最后放 82。 结果[9, 10, 82]最后合并左半区[3, 27, 38, 43]和右半区[9, 10, 82]比较过程这里最能体现归并排序的精髓两个指针分别扫描两个数组 3 vs 9 → 取 3 27 vs 9 → 取 9 27 vs 10 → 取 10 27 vs 82 → 取 27 38 vs 82 → 取 38 43 vs 82 → 取 43 剩余82 → 取 82 最终结果[3, 9, 10, 27, 38, 43, 82]整个排序完成。你可以看到每一次 merge 操作都是在处理两个“已经有序”的区间这是归并排序能够高效工作的大前提。4. C语言完整实现归并排序下面给出可编译运行的完整 C 语言代码。代码包含三部分merge函数、mergeSort函数和主函数测试。建议你在自己的编译器里新建一个.c文件把代码粘贴进去运行。// 文件路径merge_sort_demo.c #include stdio.h #include stdlib.h // 打印数组方便观察排序前后结果 void printArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } printf(\n); } // 合并两个有序区间 // 左半区间 [left, mid] // 右半区间 [mid1, right] void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; // 左半区间元素个数 int n2 right - mid; // 右半区间元素个数 // 申请临时数组保存左右区间的数据 int *L (int*)malloc(n1 * sizeof(int)); int *R (int*)malloc(n2 * sizeof(int)); if (L NULL || R NULL) { printf(内存分配失败\n); exit(1); } // 拷贝数据到临时数组 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]; } // 合并两个有序数组到 arr[left..right] int i 0; // L 的遍历下标 int j 0; // R 的遍历下标 int k left; // 原数组的写入位置 while (i n1 j n2) { // 注意使用 保证排序稳定性 if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } // 如果 L 中还有剩余元素直接拷贝到 arr while (i n1) { arr[k] L[i]; i; k; } // 如果 R 中还有剩余元素直接拷贝到 arr while (j n2) { arr[k] R[j]; j; k; } // 释放临时数组 free(L); free(R); } // 归并排序主函数 // arr待排序数组 // left排序区间左边界下标 // right排序区间右边界下标 void mergeSort(int arr[], int left, int right) { // 递归终止条件区间内只有一个元素或没有元素 if (left right) { return; } // 计算中间位置防止 (leftright) 溢出写成 left (right-left)/2 int mid left (right - left) / 2; // 递归排序左半区间 mergeSort(arr, left, mid); // 递归排序右半区间 mergeSort(arr, mid 1, right); // 合并两个有序区间 merge(arr, left, mid, right); } int main() { int arr[] {38, 27, 43, 3, 9, 82, 10}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); mergeSort(arr, 0, n - 1); printf(排序后); printArray(arr, n); return 0; }这段代码有几个细节值得单独说明。第一mid的计算用了left (right - left) / 2而不是(left right) / 2。后者在left right特别大时可能整型溢出前者可以规避这个边界问题。这是一个非常好的编程习惯在 LeetCode 题解里也经常能看到。第二merge 函数里两个while循环负责处理“剩余元素”。因为两个临时数组的长度不一定相同合并后必然有一个数组会先被取空另一个还有剩余。直接循环拷贝剩余元素即可。第三比较时用的是而不是。当L[i]等于R[j]时优先取左半边的元素。这是归并排序稳定性的关键来源。5. 运行验证与过程追踪编译运行上面的代码输出如下排序前38 27 43 3 9 82 10 排序后3 9 10 27 38 43 82如果结果和这段输出不一样优先检查 merge 函数里的下标逻辑。为了方便调试你可以在 merge 函数开始时打印当前要合并的区间printf(合并区间 [%d, %d] 和 [%d, %d]\n, left, mid, mid1, right);这样程序运行时会输出类似下面的信息合并区间 [0, 0] 和 [1, 1] 合并区间 [2, 2] 和 [3, 3] 合并区间 [0, 1] 和 [2, 3] 合并区间 [4, 4] 和 [5, 5] 合并区间 [4, 5] 和 [6, 6] 合并区间 [0, 3] 和 [4, 6]从这组输出你可以清晰地看到递归的执行顺序先完全处理左半区再处理右半区最后合并整个区间。5.1 用调试器观察递归调用栈如果你使用 VS Code GCC、Visual Studio 或者 CLion 等 IDE可以在mergeSort函数的if (left right)那一行打断点观察递归调用栈。你会看到第一次调用mergeSort(arr, 0, 6)进入后调用mergeSort(arr, 0, 3)再调用mergeSort(arr, 0, 1)再调用mergeSort(arr, 0, 0)此时触发left right直接返回然后回到上一层调用mergeSort(arr, 1, 1)返回再执行 merge合并[0, 0]和[1, 1]。这个“先深入左子树再处理右子树最后合并”的模式和二叉树的后序遍历非常相似。如果你学过树的遍历会发现归并排序的递归结构天然形成一棵递归树。6. 复杂度分析为什么归并排序性能稳定6.1 时间复杂度设归并排序处理 n 个元素的时间为 T(n)。一次归并排序可以写成递推式T(n) 2 * T(n/2) O(n)其中2 * T(n/2)是递归处理左右两个半区的时间O(n)是一次合并的时间。用主定理Master Theorem或者逐层展开推导T(n) 2T(n/2) O(n) 2(2T(n/4) O(n/2)) O(n) 4T(n/4) 2O(n) 8T(n/8) 3O(n) ... n * T(1) log2(n) * O(n) O(n log n)也就是说归并排序的时间复杂度是O(n log n)无论输入数据是正序、逆序还是乱序这个复杂度都成立。这一点和快速排序不同——快速排序在最坏情况下比如每次选的基准值都是最大值或最小值会退化到 O(n²)而归并排序没有这个缺陷。6.2 空间复杂度归并排序的空间复杂度是 O(n)因为它每次 merge 时都会分配临时数组。如果把递归调用栈的开销也算进去空间复杂度就是 O(n log n)但通常我们简化为 O(n)。相比之下排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定从表格可以看到归并排序的核心优势是无论什么情况它都能保持 O(n log n) 的时间复杂度并且保证稳定性。这个特性让它特别适合两类场景对稳定性有要求的排序。比如成绩排序总分相同的人希望按学号排序稳定排序能保证第一轮的相对顺序在第二轮不会被破坏。外部排序的基石。当数据量太大、内存放不下时可以把大文件拆成多个小块分别排序后再用归并的思路把多个有序文件合并成一个有序文件。6.3 为什么不总是用归并排序归并排序虽然稳定且复杂度优秀但它有一个硬伤额外内存开销 O(n)。在嵌入式开发、单片机编程或者内存极其受限的场景里O(n) 的额外空间是很大的负担。这时开发者会更倾向于“原地”排序的快速排序或堆排序。另一个原因是缓存局部性。归并排序需要频繁地把数据拷贝到临时数组再写回而快速排序是在原数组上交换元素对 CPU 缓存的利用更友好。所以在实际工程中很多排序库默认采用的是快速排序或优化过的混合排序而不是归并排序。但归并排序在“大数据量外部排序”和“需要稳定排序”的场合仍是不可替代的存在。7. 递归过程拆解代码到底是怎么执行的为了彻底解决“看得懂代码、想不通过程”的问题这里手动展开一次递归调用。以mergeSort(arr, 0, 6)为例mergeSort(arr, 0, 6) ├── mid 3 ├── mergeSort(arr, 0, 3) │ ├── mid 1 │ ├── mergeSort(arr, 0, 1) │ │ ├── mid 0 │ │ ├── mergeSort(arr, 0, 0) → 直接返回 │ │ ├── mergeSort(arr, 1, 1) → 直接返回 │ │ └── merge(arr, 0, 0, 1) → 合并 [38] 和 [27]得到 [27, 38] │ ├── mergeSort(arr, 2, 3) │ │ ├── mid 2 │ │ ├── mergeSort(arr, 2, 2) → 直接返回 │ │ ├── mergeSort(arr, 3, 3) → 直接返回 │ │ └── merge(arr, 2, 2, 3) → 合并 [43] 和 [3]得到 [3, 43] │ └── merge(arr, 0, 1, 3) → 合并 [27, 38] 和 [3, 43]得到 [3, 27, 38, 43] ├── mergeSort(arr, 4, 6) │ ├── mid 5 │ ├── mergeSort(arr, 4, 5) │ │ ├── mid 4 │ │ ├── mergeSort(arr, 4, 4) → 直接返回 │ │ ├── mergeSort(arr, 5, 5) → 直接返回 │ │ └── merge(arr, 4, 4, 5) → 合并 [9] 和 [82]得到 [9, 82] │ ├── mergeSort(arr, 6, 6) → 直接返回 │ └── merge(arr, 4, 5, 6) → 合并 [9, 82] 和 [10]得到 [9, 10, 82] └── merge(arr, 0, 3, 6) → 合并 [3, 27, 38, 43] 和 [9, 10, 82]得到最终有序数组仔细看这幅展开图你会发现一个规律mergeSort 的顺序是固定的“左 → 右 → 合并”。它先把整个问题一分为二对左边部分完全处理完之后再处理右边最后两边合并。为什么递归最后能正确工作因为每次 merge 的前提是“左右两个区间已经各自有序”。这个前提由递归调用保证递归进入时先把区间拆到只剩一个元素一个元素天然有序再一层层合并回去每次合并后的区间都是有序的。这就是所谓的“数学归纳法式的正确性”。8. 常见问题与排查思路下面是初学者写归并排序时最常踩的坑我整理成了表格方便你对照排查。问题现象可能原因排查方式解决方案程序崩溃提示数组越界merge 函数里 left、mid、right 边界计算错误打印每次 merge 的区间边界检查n1 mid - left 1和n2 right - mid是否算对区间为闭区间[left, right]计算长度时左闭右闭要 1递归无法终止栈溢出递归终止条件写错比如只写了left right检查是否存在left right的情况统一使用if (left right) return;排序结果错误但无崩溃merge 中漏掉了某个剩余数组的拷贝循环手动模拟一个 3 元素数组的合并过程必须包含两个 while 循环分别处理 L 和 R 的剩余元素内存分配失败导致异常临时数组 malloc 后没有判断返回 NULL增加判空逻辑并输出错误信息生产代码中if (L NULL || R NULL) exit(1);结果正确但排序不稳定合并时用了而不是用相同元素构造测试用例如[2, 1, 2]相等时先取左区间元素使用Visual Studio 提示 scanf 不安全使用了scanf相关函数VS 强制要求安全版本确认是否非要用 scanf学习阶段可用scanf_s注意参数格式不同其中最隐蔽的是“合并时漏拷贝剩余元素”。新手容易写完while (i n1 j n2)的循环后就直接结束函数结果发现数组中有一块区域的值没有写回原数组。这个 bug 在数组长度为偶数时不容易暴露一旦数组长度是奇数就会出现莫名的 0 或垃圾值。建议平时测试时多用奇数长度的数组。另一个高频错误是“修改了原数组但没有同步修改 mid”。比如有人图省事在mergeSort里直接写int mid (left right) / 2;这没有问题但如果在递归调用时把right写成mid就把右半区间漏掉了导致右侧元素永远排不到序。9. 归并排序与快速排序的对比谁才是更优解既然题目热搜词里包含了“快速排序 c 语言”这里专门做一次对比。学归并排序时很多人会问快速排序平均也是 O(n log n)而且原地排序、空间占用小为什么还要学归并排序这个问题的答案可以从三个层面看。第一稳定性。归并排序是稳定排序快速排序是不稳定排序。如果业务要求“先按分数排序分数相同的人保持原来的先后顺序”归并排序是天然合适的快速排序则做不到。第二最坏时间复杂度。快速排序在最坏情况下每次选取的基准都是极值时间复杂度是 O(n²)。虽然随机化基准可以降低这个概率但无法彻底消除。归并排序不存在这个问题它的 O(n log n) 是“无条件的”。第三递归结构。两者的递归结构非常不同。快速排序是“先分区再递归”的顺序归并排序是“先递归到底再合并”的顺序。理解归并排序的“后序合并”后再看快速排序的“前序分区”会更容易形成体系化认知。但在工程层面快速排序通常在大多数场景下更快。原因是它访问内存的模式更简单、缓存命中率更高不需要大量拷贝。归并排序的应用重心是外部排序和稳定性要求高的场景两者并不矛盾。10. 优化思路与扩展学习归并排序基础版本已经能够解决大部分问题但在工程中还有一些常见优化手段值得了解。10.1 小数组用插入排序递归到区间很小的时候比如数组长度小于 10 或 16可以不再继续递归而是改用插入排序。原因是插入排序在数组接近有序时表现很好而且没有递归调用和临时数组分配的开销。很多工业级的排序实现都会做这种“混合排序”优化。#define INSERTION_THRESHOLD 10 void mergeSortOptimized(int arr[], int left, int right) { if (right - left 1 INSERTION_THRESHOLD) { // 改用插入排序处理小数组 for (int i left 1; i right; i) { int key arr[i]; int j i - 1; while (j left arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } return; } int mid left (right - left) / 2; mergeSortOptimized(arr, left, mid); mergeSortOptimized(arr, mid 1, right); merge(arr, left, mid, right); }10.2 复用临时数组基础版本的 merge 每次排序时都 malloc 一块新内存频繁分配会影响性能。更常用的做法是在 mergeSort 外层只申请一次和原数组等大的临时数组然后把它作为参数传给 merge 函数。每次 merge 都使用同一块临时空间能显著减少运行时开销。10.3 归并排序的逆序对应用归并排序还有一个经典应用计算数组中的逆序对数量。在合并过程中如果左半边的某个元素大于右半边的某个元素那么左半边从当前位置到 mid 的所有元素都与右半边的这个元素构成逆序对。用这一思路可以在 O(n log n) 时间内完成统计面试中也很常考。11. 常见面试题与笔试高频考点归并排序是计算机二级、校招笔试和考研数据结构的热门考点。这里列几个最常见的追问读者可以自测是不是都能答得上来。归并排序是稳定的吗为什么是稳定的。因为合并时遇到相等元素会优先取左半区间的元素保持了原数组中的相对顺序。归并排序的空间复杂度是多少O(n)。额外空间主要来自合并时创建的临时数组。归并排序适合链表吗很适合。链表不适合快速排序的随机访问但归并排序只需要顺序访问用它给链表排序是很经典的实现。归并排序和快速排序的本质区别是什么归并排序的关键操作在“合并”递归发生在处理数据之前或之后没有本质区别快速排序的关键操作在“分区”数据移动发生在递归之前。归并排序时间稳定但空间大快速排序空间小但最坏情况可能退化。每次合并后数组一定有序吗是的。合并的前提是左右两个区间已经有序二路归并保证合并后的区间也是有序的。如果上面的问题都能顺利回答说明你对归并排序理解得已经足够扎实可以进入下一步手把手把归并排序改成链表版本或者尝试写一个不使用递归的归并排序。12. 给你的下一步建议从学习路径上看归并排序之后值得继续深入的内容有三个方向。先掌握概念的联系。归并排序、快速排序、堆排序都是“排序算法”这个主题下的分支但它们背后的策略不同。归并排序是“分治 递归合并”快速排序是“分治 原地分区”堆排序是“基于完全二叉树的选择排序”。把三者的代码和过程放在一起对比会比孤立的背诵效果好很多。然后动手刷题验证。力扣上有不少归并排序相关的题目比如排序数组、翻转对、计算右侧小于当前元素的个数。不需要刷很多两三道中等难度的题就足够检验你对“归并思想”的理解。最后接触真实场景。如果你的方向是后端开发或大数据找一份大数据量文件排序相关的开源代码看看外部排序如何利用归并思想。如果你做嵌入式开发可以思考如何用有限的 RAM 完成局部排序。技术只有落到场景里才算真正学会了。写归并排序的 C 语言代码本质上就是在练习两个能力递归地分解问题以及细致地处理边界条件。这两种能力是算法工程师和优秀开发者的基本功。建议你把代码复制下来多改几个数组长度多打印几次中间结果直到能不看参考代码独立写出为止。排序算法不需要背写多了自然就记住了。