归并排序是C语言算法学习中绕不开的经典也是很多零基础读者第一次感受到递归威力的地方。这个排序的核心思想并不复杂如果手上有两个已经排好序的序列那么只要用一个双指针循环就能在线性时间内合并出一个新的有序序列如果一开始没有有序序列就先把数组拆成单个元素单元素天然有序再两两合并。真正让人卡住的部分通常是递归边界、临时数组管理和合并完成后如何把数据写回原数组。这篇文章从最小的子问题开始讲逐步写出递归版和非递归版的C语言归并排序代码并给出调试、验证和进阶练习方法。学完之后你应该能独立写出稳定、可运行的归并排序代码也能把它扩展到逆序对统计和链表排序场景。1. 归并排序要解决什么问题先看懂合并两个有序数组1.1 最核心的子问题两个有序数组合并成一个有序数组假设手上有两个已经排好序的数组例如1 3 5和2 4 6想把它们合并成一个大数组1 2 3 4 5 6。最笨的办法是全部放进一个数组再排序但这样浪费了“子序列已经有序”这个信息。归并排序的做法是使用两个指针指针i指向第一个有序序列当前元素。指针j指向第二个有序序列当前元素。比较arr[i]和arr[j]较小的元素先放入结果数组。放入结果数组后对应指针向后移动。当其中一个序列被取完把另一个序列剩余部分直接复制到结果数组。用 C 语言描述最核心的比较和移动逻辑就是这样while (i mid j right) { if (arr[i] arr[j]) { temp[t] arr[i]; } else { temp[t] arr[j]; } }这里mid是左半区间的结束位置j从mid 1开始temp是临时数组。比较时写成而不是是有原因的当两个值相等时优先取左边序列的元素这样排序前位于左边的相同值排序后仍然位于左边归并排序因此是稳定排序。1.2 分治思想把一个无序大数组拆成两个更小的数组合并两个有序数组本身不能排序因为原始数组是无序的。这时要用到分治思想如果数组本身只有一个元素它天然有序如果数组有多个元素就把它从中间切开递归排序左半部分和右半部分等左右两部分都有序后再合并。用一张拆分顺序图可以看得更清楚。假设数组是38 27 43 3 9 82 10拆分过程是38 27 43 3 9 82 10 ├── 38 27 43 3 │ ├── 38 27 │ │ ├── 38 │ │ └── 27 │ └── 43 3 │ ├── 43 │ └── 3 └── 9 82 10 ├── 9 82 │ ├── 9 │ └── 82 └── 10拆分到单元素后整个数组都是由“天然有序”的单个元素组成的接下来要做的事情就是不断合并把有序子数组的长度从 1 变成 2、从 2 变成 4最终变成整个数组长度。1.3 复杂度与稳定性为什么归并排序值得学归并排序的时间复杂度稳定在O(n log n)最坏情况也是O(n log n)这是它比快速排序更可控的地方。递归拆分数组大约需要log2 n层每一层合并所有元素的总代价是O(n)所以总复杂度是O(n log n)。空间复杂度是O(n)因为合并时需要一块和原数组等长的临时数组。它也不是原地排序算法。排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n^2)O(log n)不稳定冒泡排序O(n^2)O(n^2)O(1)稳定从学习角度看归并排序是理解分治、递归调用栈、双指针合并和空间换时间策略的一块很好的跳板。很多初学者觉得它比冒泡排序难是因为冒泡排序只需要一层循环和一次交换而归并排序需要拆成“递归函数”和“合并函数”两部分还要处理临时数组的回写。这篇文章后续的代码会把这两个函数拆得很清楚。2. 写代码前的准备区间定义、临时数组和环境2.1 用命令行编译器跑通最小环境在学习阶段不一定要先打开 IDE。使用命令行编译器能让你更清楚地看到编译、运行、报错这一整条链路。推荐安装gcc装好后先检查版本gcc --version如果能看到类似gcc (GCC) 13.x.x的输出说明编译器可用。用 VS Code 写代码时只需要安装 C/C 扩展然后在终端里编译运行。一个最简单的编译命令是gcc -Wall -Wextra -o merge_sort merge_sort.c ./merge_sort-Wall和-Wextra会打开常见警告。初学者写归并排序很容易出现变量声明了但没使用、数组下标可能越界等问题编译器的警告是第一条防线。如果本机没有安装gcc使用在线编译器也能运行本文示例代码但要注意在线编译器通常对运行内存和时间有限制验证小数组排序没有问题做大规模随机测试时还是建议使用本机环境。2.2 区间定义选择左闭右闭区间C 语言数组下标从0开始归并排序最常见的区间写法是左闭右闭区间[left, right]意思是数组中第left个元素到第right个元素都参与本次排序。区间长度是right - left 1。中间位置mid left (right - left) / 2。左半部分是[left, mid]。右半部分是[mid 1, right]。递归终止条件是left right表示当前区间长度不超过 1。mid的计算建议写成left (right - left) / 2而不是(left right) / 2。如果数组特别大left right有可能超过int能表示的范围导致结果变成负数。虽然普通学习场景不会遇到这种极端情况但养成这个习惯没有坏处。区间定义不同会导致后续所有代码边界不同。很多初学者把左闭右闭和左闭右开混着写结果排序后出现元素丢失或重复。后面排查部分会专门讨论这类问题。2.3 临时数组只分配一次不要每层递归都分配归并排序需要一块临时数组暂存合并结果。一个典型误区是在merge函数内部每次调用malloc这样虽然代码看起来简单但每次归并都要申请和释放内存性能很差而且如果忘记free还会造成内存泄漏。推荐做法是在main函数里一次性分配一块长度为数组总长度的临时数组然后把它的指针传给递归函数和合并函数int *temp (int *)malloc(len * sizeof(int)); if (temp NULL) { printf(malloc failed\n); return 1; }分配失败一定要处理。学习阶段数组比较小几乎不会失败但在作业题或竞赛题中数组可能开到几十万甚至上百万指针返回NULL后程序继续运行会直接段错误。分配方式优点缺点使用建议每层递归分配代码局部性看起来好性能差容易内存泄漏不建议全局或 main 分配一次性能好逻辑清晰需要多传一个参数推荐使用静态数组无需手动释放数组大小固定不灵活仅用于学习小数组3. 递归版归并排序C语言完整实现与过程拆解3.1 第一步编写 merge 函数合并两个有序区间merge函数负责把同一个数组中的两个相邻有序区间合并成一个大的有序区间。两个区间的范围是[left, mid]和[mid 1, right]。完整实现如下#include stdio.h #include stdlib.h 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]; } int k left; t 0; while (k right) { arr[k] temp[t]; } }这段代码里需要注意的点i从left开始j从mid 1开始两个指针分别对应两个有序区间。第一个while是双指针比较哪个元素小就先把哪个放入temp。第二个和第三个while负责处理剩余元素。因为两个区间长度不一定相等总有一个区间会先耗尽。最后一步要把temp中的内容回写到arr的对应位置。如果漏掉这一步排序结果不会出现在原数组中这也是归并排序最常见的问题之一。temp的下标直接从 0 开始即可因为最后回写时是针对[left, right]这段区间而不是整个数组。3.2 第二步编写 mergeSort 递归函数递归函数负责把数组拆到足够小再调用merge完成合并。逻辑非常直观void mergeSort(int arr[], int left, int right, int temp[]) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); }递归执行顺序可以描述如下先判断区间是否已经不需要排序也就是区间里只有一个元素或没有元素。计算出中间位置。递归排序左半部分。递归排序右半部分。左右两部分都有序后合并它们。在递归排序左半部分时程序会一路走到底直到左半部分也被拆成单元素区间。这个“先拆左边、再拆右边、最后合并”的顺序可以通过缩进打印递归调用来观察稍后会给出调试方法。3.3 完整示例代码与运行结果把merge、mergeSort和一个简单的main函数组合起来就是一份最小可运行代码#include stdio.h #include stdlib.h 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]; } int k left; t 0; while (k right) { arr[k] temp[t]; } } void mergeSort(int arr[], int left, int right, int temp[]) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } void printArray(int arr[], int len) { for (int i 0; i len; i) { printf(%d , arr[i]); } printf(\n); } int main(void) { int arr[] {38, 27, 43, 3, 9, 82, 10}; int len sizeof(arr) / sizeof(arr[0]); int *temp (int *)malloc(len * sizeof(int)); if (temp NULL) { printf(malloc failed\n); return 1; } printf(排序前: ); printArray(arr, len); mergeSort(arr, 0, len - 1, temp); printf(排序后: ); printArray(arr, len); free(temp); return 0; }编译运行后预期输出排序前: 38 27 43 3 9 82 10 排序后: 3 9 10 27 38 43 82sizeof(arr) / sizeof(arr[0])是 C 语言求数组长度的常见写法。这个写法只在“数组名”还未退化为指针时有效所以不要在函数内部对一个传入的数组参数执行这一句。3.4 用手推过程理解每一轮合并只看代码很难建立直观感受建议对照下面的拆分表格和合并表格走一遍。原始数组38 27 43 3 9 82 10拆分过程层数左半部分右半部分第一层38 27 43 39 82 10第二层38 2743 3第三层3827第三层433第二层右侧9 8210合并过程按递归返回顺序进行合并顺序合并区间合并结果第 1 次[0..0] 与 [1..1]27 38 43 3 9 82 10第 2 次[2..2] 与 [3..3]27 38 3 43 9 82 10第 3 次[0..1] 与 [2..3]3 27 38 43 9 82 10第 4 次[4..4] 与 [5..5]3 27 38 43 9 82 10第 5 次[4..5] 与 [6..6]3 27 38 43 9 10 82第 6 次[0..3] 与 [4..6]3 9 10 27 38 43 82这个表格本质上是归并排序“文字动画”的关键帧。如果能把每一轮合并后的数组打印出来你看到的就是一个逐步有序的过程。4. 非递归归并排序不写递归也能完成二路归并4.1 为什么要学非递归版本递归版归并排序好懂但有两个问题一是递归调用栈在极端情况下仍然可能成为限制二是在某些嵌入式或底层开发中使用递归需要格外谨慎。非递归版本用循环控制每次合并的区间宽度逻辑上更能体现归并排序“先相邻合并再扩大合并范围”的本质。递归版和非递归版的对比维度递归版非递归版代码可读性高分治结构清晰中边界判断较多递归栈依赖依赖函数调用栈不依赖合并顺序深度优先先拆到最小再合并宽度优先按块长度循环适用场景学习、普通工程嵌入式、外部排序思想理解4.2 核心流程宽度从 1 开始成倍增加非递归归并排序的思路是一开始把整个数组看成很多个长度为 1 的有序块然后每两个相邻块合并成长度为 2 的有序块下一次再把长度为 2 的块两两合并成长度为 4 的块。直到当前块宽度超过数组长度整个数组就有序了。用代码描述外层和内层循环void mergeSortIterative(int arr[], int len) { int *temp (int *)malloc(len * sizeof(int)); if (temp NULL) { return; } for (int width 1; width len; width * 2) { for (int left 0; left len; left 2 * width) { int mid left width - 1; if (mid len - 1) { continue; } int right left 2 * width - 1; if (right len) { right len - 1; } merge(arr, left, mid, right, temp); } } free(temp); }解释几个关键点width是当前每个有序块的长度初始为 1。内层循环每次处理两个相邻块左块范围是[left, mid]右块范围是[mid 1, right]。mid left width - 1这是左块的结束位置。如果mid len - 1说明当前块已经是数组最后一块没有右块可以合并直接跳过。正常的右边界是left 2 * width - 1但数组末尾可能凑不齐长度所以如果越界要裁剪到len - 1。这里复用了前面的merge函数因为合并逻辑完全相同。4.3 非递归版本运行验证把mergeSortIterative放进之前的测试程序替换main中的调用mergeSortIterative(arr, len);对{38, 27, 43, 3, 9, 82, 10}运行后的输出与递归版完全一致排序前: 38 27 43 3 9 82 10 排序后: 3 9 10 27 38 43 82非递归版本最容易犯错的地方是最后的边界处理。可以单独打印每一轮的left、mid、right来观察区间是否正确尤其是数组长度不是 2 的幂时右边界裁剪那一步不能漏。5. 排序结果不对怎么办调试思路和高频错误排查5.1 用随机数组和 qsort 对比验证正确性学习算法时只用一组数据验证远远不够。推荐写一个小测试函数生成随机数组用自己写的归并排序排序再用 C 标准库的qsort对同样数据排序最后逐个元素比较。#include stdlib.h int compareInt(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void testRandomSort() { for (int n 1; n 1000; n) { int *arr (int *)malloc(n * sizeof(int)); int *expected (int *)malloc(n * sizeof(int)); for (int i 0; i n; i) { arr[i] rand() % 1000; expected[i] arr[i]; } mergeSort(arr, 0, n - 1, temp); qsort(expected, n, sizeof(int), compareInt); for (int i 0; i n; i) { if (arr[i] ! expected[i]) { printf(mismatch at n%d, index%d\n, n, i); free(arr); free(expected); return; } } free(arr); free(expected); } printf(all test passed\n); }这个测试能覆盖大量随机情况比人工肉眼检查可靠得多。注意示例中的temp需要在测试前分配并且长度为n。5.2 打印递归调用过程理解程序执行顺序如果递归逻辑混乱可以在mergeSort中增加缩进日志打印每次排序的区间void mergeSortDebug(int arr[], int left, int right, int temp[], int depth) { for (int i 0; i depth; i) { printf( ); } printf(sort [%d..%d]\n, left, right); if (left right) { return; } int mid left (right - left) / 2; mergeSortDebug(arr, left, mid, temp, depth 1); mergeSortDebug(arr, mid 1, right, temp, depth 1); merge(arr, left, mid, right, temp); }对长度为 7 的数组调用后输出大致为sort [0..6] sort [0..3] sort [0..1] sort [0..0] sort [1..1] sort [2..3] sort [2..2] sort [3..3] sort [4..6] sort [4..5] sort [4..4] sort [5..5] sort [6..6]从输出可以清楚看出程序并不是先处理完整个左半部分再处理右半部分而是优先递归到最深层然后逐层返回并合并。理解了递归执行顺序排查越界问题会容易很多。5.3 高频错误排查表问题现象可能原因检查方式处理建议排序后数组没有变化merge最后没有把temp回写到arr在merge末尾打印arr确认回写while (k right) arr[k] temp[t]程序运行崩溃递归无限执行缺少递归终止条件或终止条件写错检查if (left right) return递归函数第一行就写终止条件数组中出现重复元素或元素丢失左闭右闭与左闭右开混用mid或right边界写错打印每次left, mid, right统一使用[left, right]左半部分到mid右半部分从mid 1开始大数组运行段错误malloc分配失败后没有判空或下标越界检查返回值编译时加-fsanitizeaddress分配后判空用地址检查工具运行奇数长度数组排序错误非递归版本没有处理最后一组right越界打印每一轮的rightright min(left 2 * width - 1, len - 1)排序结果不稳定合并时写成if (arr[i] arr[j])而不是构造相同关键字的输入测试相等时优先取左侧元素在函数内部用sizeof(arr)求长度错误数组参数已经退化为指针打印sizeof(arr)观察值在外部把长度作为参数传入5.4 把排序过程变成文字动画很多人对“动画讲解”没有概念其实用printf打印关键步骤就能形成最简单的文字动画。在每次merge结束后调用printArray可以看到数组逐步变得有序。为了看得更明显还可以让程序短暂暂停#include unistd.h // 在 merge 末尾加上 printArray(arr, len); // sleep(1);输出效果类似27 38 43 3 9 82 10 27 38 3 43 9 82 10 3 27 38 43 9 82 10 3 27 38 43 9 82 10 3 27 38 43 9 10 82 3 9 10 27 38 43 82这种逐行打印的过程就是理解归并排序执行顺序的关键。如果想做成真正的可视化可以在此基础上用文件输出或图形库展示但核心思路仍然是“每轮合并后呈现一次状态”。6. 归并排序的进阶用法、常见题型与学习建议6.1 统计逆序对归并排序最经典扩展所谓逆序对是指数组中一对下标i j但arr[i] arr[j]的元素对。求逆序对数量如果暴力两层循环时间复杂度是O(n^2)利用归并排序可以在合并阶段顺便统计把复杂度降到O(n log n)。原理是当合并[left, mid]和[mid 1, right]时如果发现arr[i] arr[j]说明左区间中从i到mid的所有元素都大于arr[j]。于是逆序对数量 mid - i 1示例代码片段long long inversion 0; void mergeCount(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 { inversion (mid - i 1); temp[t] arr[j]; } } while (i mid) { temp[t] arr[i]; } while (j right) { temp[t] arr[j]; } int k left; t 0; while (k right) { arr[k] temp[t]; } }需要注意逆序对数量可能非常大使用long long而不是普通的int。6.2 链表排序归并排序比快速排序更适合链表在 C 语言中对于单向链表做排序快速排序通常不太方便因为需要随机访问和中轴值交换归并排序只需要改指针非常适合链表。核心思路是用快慢指针找到链表中点。递归排序左半段和右半段。合并两个有序链表。具体接口可以设计成struct Node { int data; struct Node *next; }; struct Node *getMiddle(struct Node *head); struct Node *mergeList(struct Node *l1, struct Node *l2); struct Node *mergeSortList(struct Node *head);合并链表的逻辑和数组归并几乎一样区别是数组用下标访问链表用next指针访问。练习这个题目能进一步巩固归并排序的分治思想。6.3 从内存排序到外部排序当数据量大到无法全部装入内存时普通排序算法就不能直接使用了。外部排序的基本思想仍然是归并先把大文件切分成多个能读入内存的块每块排序后写到磁盘再用多路归并把多个有序块合并成一个更大的有序块。归并排序在这里并不只是一个考试知识点而是一整套“分而治之”方法的源头。理解数组归并后再理解“多路归并”“败者树”等外部排序优化会有更好基础。6.4 两小时学习计划与自测清单如果目标是“零基础 2 小时搞懂归并排序”可以参考下面这个节奏时间段任务验证目标0 - 30 分钟理解合并两个有序数组手写双指针合并能解释i、j、t三个指针的移动过程30 - 60 分钟理解递归拆分画出递归调用树能说出为什么单元素天然有序60 - 90 分钟写递归版归并排序跑通示例用随机数组和qsort对比验证90 - 105 分钟写非递归版归并排序多组数据结果与递归版一致105 - 120 分钟做逆序对统计或链表排序题目能解决一道归并排序扩展题学习过程中可以自测以下问题归并排序的时间复杂度、空间复杂度、稳定性分别是什么为什么如果merge函数最后不回写数组程序会发生什么合并时使用和对稳定性有什么影响数组长度为奇数时非递归版本的右边界如何处理为什么临时数组只分配一次而不是每层递归都分配归并排序这门功课最关键的不是把代码背下来而是把“合并两个有序数组”这个子问题理解透。递归只是让数组能够被拆到符合条件的方式真正决定排序结果正确性的是每一个合并步骤里的边界和回写逻辑。把这一步写稳、调通后续的逆序对、链表排序、外部排序等题目都会迎刃而解。