C语言归并排序详解：从递归分治到完整代码实现

很多学习 C 语言的同学都会有这种感觉：冒泡排序和选择排序刚弄明白，一看到归并排序就懵了。代码不长，但递归一层套一层，return 来 return 去，脑子完全跟不上程序执行顺序。即使勉强背下了代码，过两个星期再写，还是不会。

这不是你笨，而是学习路径出了问题。

归并排序真正的难点不在于代码本身，而在于两个关键点：一是你还没在脑袋里形成“整个数组被不断拆成两半，再两两合并回去”的动态画面；二是你还没理解递归在这里其实是一种“先递后归”的控制结构，而不是数学公式。

这篇文章的目标很直接：用尽可能通俗的方式，把归并排序的分治思想、图解过程、C 语言完整实现、复杂度分析一次讲透。你不需要任何算法基础，只要会 C 语言的函数和数组，就能跟着写完整个排序代码。代码部分我会给出可直接编译运行的完整版本，同时讲解面试中常问的细节和优化点。

1. 归并排序到底解决了一个什么问题

如果只看结论，归并排序是建立在“合并两个有序数组”这个基础操作之上的排序算法。

这里先说一个核心判断：归并排序的难点不在“排序”，而在“合并”。排序本身是靠递归不断把问题变小，真正干活的是合并两个已经有序的子数组。你只要把 merge 这个函数吃透了，整个归并排序就通关了一大半。

想想看，如果给你两个已经排好序的数组：

A = [1, 4, 7, 9] B = [2, 3, 5, 8]

你愿意不愿意把它们合并成一个有序的大数组？这太简单了。两个数组从左往右各拿一个数出来比大小，谁小谁先进新数组。这就是归并排序最基本的一步。

但问题来了，原始数组通常是乱序的：

[38, 27, 43, 3, 9, 82, 10]

它根本没有两个现成的有序子数组可以合并。那怎么办？

归并排序的想法非常直接：如果数组长度为 1，它天然有序；如果数组长度为 2，比较一下就能排好；如果更长，就把它一分为二，把左半边排好序，把右半边排好序，最后再把这两个有序半区合并起来。

这里体现的正是分治策略：

• 分：把一个大数组从中间切成两个子数组。
• 治：递归地对每个子数组再切分，直到子数组只剩一个元素。
• 合：从最小的子数组开始，两两合并出有序数组，最终合并成完整的有序数组。

这种思路相比冒泡排序有一个本质区别：冒泡排序每一轮都盯着整个数组做交换，而归并排序先把问题拆小，再在小规模上解决，最后合并答案。

从实际编码角度讲，归并排序也是一种你必须掌握的“模板型算法”。很多复杂问题，比如求逆序对数量、链表排序、外部排序，底层都用到了归并思想。学透归并排序，不只是会写一个排序函数，更是掌握一种解决规模问题的思维框架。

2. 归并排序动画级理解：从一棵递归树看全过程

很多教材直接丢给你一段归并排序代码，然后让你背。这样学效率很低。我们先把代码放在一边，用图的方式把全过程走一遍。

待排序数组：

下标： 0 1 2 3 4 5 6 数值： 38 27 43 3 9 82 10

第一步：拆分。

我们把数组从中间一分为二：

左半区：[38, 27, 43, 3] 右半区：[9, 82, 10]

注意，这里并不真的创建新数组，在 C 语言里是通过下标范围来划分逻辑区域的。继续拆分：

[38, 27, 43, 3] 拆成 [38, 27] 和 [43, 3] [9, 82, 10] 拆成 [9] 和 [82, 10]

再继续拆：

[38, 27] 拆成 [38] 和 [27] [43, 3] 拆成 [43] 和 [3] [82, 10] 拆成 [82] 和 [10]

到这里，每个子数组的长度都是 1。长度为 1 的数组天然有序，不用再拆了。

第二步：合并。

现在从最底层开始两两合并。先看 [38] 和 [27]，比较大小，得到：

[27, 38]

再看 [43] 和 [3]，得到：

[3, 43]

此时左半区的第二层变成了：

[27, 38] 和 [3, 43]

继续合并这两个有序数组：

[3, 27, 38, 43]

左半区排好了。再看右半区：[9] 保持不变，[82] 和 [10] 合并成 [10, 82]，然后再合并：

[9, 10, 82]

最后，把左半区 [3, 27, 38, 43] 和右半区 [9, 10, 82] 合并，得到完整有序数组：

[3, 9, 10, 27, 38, 43, 82]

这就是归并排序的完整过程。拆的时候从大往小，合的时候从小往大。拆到不能再拆，就开始合并；合并的结果总是有序的，所以最终整个数组有序。

这段过程对应的递归结构可以用下面这棵递归树来表示：

[38 27 43 3 9 82 10] / \ [38 27 43 3] [9 82 10] / \ / \ [38 27] [43 3] [9] [82 10] / \ / \ / \ [38] [27] [43] [3] [82] [10]

你只要记住这棵树，归并排序的大局观就有了。平时写递归卡住时，就在草稿纸上画这棵树，对照代码看当前递归到哪一层。

3. 核心操作：合并两个有序数组

前面提到，归并排序最关键的操作是合并两个有序数组。这一部分我们必须写清楚，因为整个归并排序代码的核心就是这个 merge 函数。

假设我们有数组 arr，其中下标 left 到 mid 是有序的，下标 mid+1 到 right 也是有序的。我们的任务是把这两个区间合并成一个有序区间，覆盖回原数组。

C 语言实现如下：

// 文件路径：merge_demo.c // 功能：将 arr[left..mid] 和 arr[mid+1..right] 合并为有序区间 #include <stdio.h> #include <stdlib.h> void merge(int arr[], int left, int mid, int right) { int i, j, k; 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 (i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; } // 合并临时数组回 arr[left..right] i = 0; j = 0; k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // 如果左半区还有剩余，直接拷贝 while (i < n1) { arr[k] = L[i]; i++; k++; } // 如果右半区还有剩余，直接拷贝 while (j < n2) { arr[k] = R[j]; j++; k++; } free(L); free(R); }

这段代码的逻辑非常清晰，一共四步：

1. 算出左右两个半区的长度，申请临时数组。
2. 把原数组 left 到 mid 的数据拷到 L，把 mid+1 到 right 的数据拷到 R。
3. 用 i 和 j 分别指向 L 和 R 的起始位置，比较 L[i] 和 R[j]，把较小的放入原数组。
4. 当某个半区先遍历完，另一个半区剩余元素直接按顺序放到后面。

这里有一个容易忽略的细节：为什么不直接用一个临时数组，而要分成 L 和 R 两个临时数组？

因为合并的过程中，原数组的位置会被覆盖。如果你直接把左边元素和右边元素同时存在原数组里而不借助额外空间，前面存进去的值可能把还没比较的值覆盖掉。分成两个临时数组，是为了保证比较的两个来源数据在合并过程中不被破坏。

面试里也经常会问：能不能做到空间复杂度 O(1) 的原址归并排序？理论上有原地归并的写法，但实现非常复杂，而且常数因子很大，实际工程中很少使用。标准归并排序的空间复杂度是 O(n)，这点我们在后面复杂度分析里详细讲。

4. 完整归并排序 C 语言实现

有了 merge 函数，归并排序本身只需要做两件事：递归拆分，然后调用 merge 合并。

// 文件路径：merge_sort.c // 功能：完整归并排序实现，含测试代码 #include <stdio.h> #include <stdlib.h> // 合并函数声明 void merge(int arr[], int left, int mid, int right); // 归并排序递归函数 void mergeSort(int arr[], int left, int right) { if (left >= right) { return; // 区间内只有一个元素或为空，无需排序 } int mid = left + (right - left) / 2; // 防止整数溢出 // 递归排序左半部分 mergeSort(arr, left, mid); // 递归排序右半部分 mergeSort(arr, mid + 1, right); // 合并两个有序部分 merge(arr, left, mid, right); } void merge(int arr[], int left, int mid, int right) { int i, j, k; 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 (i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; } i = 0; j = 0; k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } free(L); free(R); } // 打印数组 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } // 主函数测试 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; }

编译运行方式：

gcc merge_sort.c -o merge_sort ./merge_sort

预期输出：

排序前：38 27 43 3 9 82 10 排序后：3 9 10 27 38 43 82

这段代码有一个容易写错的地方：mid 的计算。很多教材写int mid = (left + right) / 2;，这在 left 和 right 都很大时可能溢出。写成int mid = left + (right - left) / 2;更安全。虽然在普通测试数据里看不出差别，但面试官问起来时，你能答出这一点会加分不少。

还有一个细节：递归出口的判断条件是if (left >= right)。为什么用 >= 而不是 ==？

因为当区间为空时，可能出现 left > right 的情况。虽然正常递归里一般不会传入 left > right 的区间，但写成 >= 更严谨，也能防止意外情况导致死循环。

5. 归并排序执行过程可视化：用一个演示版代码看清每一步

如果你只运行上面的代码，看到的是排序前后的对比，中间过程还是看不见。为了真正搞懂归并排序，建议你在学习阶段加一点打印代码，把每次 merge 前后的状态输出出来。

// 文件路径：merge_sort_debug.c // 功能：归并排序过程可视化，学习用 #include <stdio.h> #include <stdlib.h> void printRange(int arr[], int left, int right) { printf("["); for (int i = left; i <= right; i++) { printf("%d", arr[i]); if (i < right) { printf(", "); } } printf("]"); } void merge(int arr[], int left, int mid, int right) { printf("合并区间 [%d..%d] 和 [%d..%d] 前：", left, mid, mid + 1, right); printf("左半区 "); printRange(arr, left, mid); printf(" + 右半区 "); printRange(arr, mid + 1, right); printf("\n"); int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; int *L = (int *)malloc(n1 * sizeof(int)); int *R = (int *)malloc(n2 * sizeof(int)); for (i = 0; i < n1; i++) L[i] = arr[left + i]; for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; i = 0; j = 0; k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; free(L); free(R); printf("合并后："); printRange(arr, left, right); printf("\n\n"); } void mergeSort(int arr[], int left, int right) { if (left >= right) { printf("区间 [%d..%d] 只有一个元素，停止拆分\n", left, right); return; } int mid = left + (right - left) / 2; printf("拆分区间 [%d..%d]，中间位置 mid=%d\n", left, right, mid); 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("初始数组："); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n\n"); mergeSort(arr, 0, n - 1); printf("最终排序结果："); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

运行这个演示版，你会看到类似下面的输出：

初始数组：38 27 43 3 9 82 10 拆分区间 [0..6]，中间位置 mid=3 拆分区间 [0..3]，中间位置 mid=1 拆分区间 [0..1]，中间位置 mid=0 区间 [0..0] 只有一个元素，停止拆分 区间 [1..1] 只有一个元素，停止拆分 合并区间 [0..0] 和 [1..1] 前：左半区 [38] + 右半区 [27] 合并后：[27, 38] 拆分区间 [2..3]，中间位置 mid=2 区间 [2..2] 只有一个元素，停止拆分 区间 [3..3] 只有一个元素，停止拆分 合并区间 [2..2] 和 [3..3] 前：左半区 [43] + 右半区 [3] 合并后：[3, 43] 合并区间 [0..1] 和 [2..3] 前：左半区 [27, 38] + 右半区 [3, 43] 合并后：[3, 27, 38, 43] 拆分区间 [4..6]，中间位置 mid=5 拆分区间 [4..4] 只有一个元素，停止拆分 ...

建议你自己跑一遍这个程序，对照输出画递归树，你会明显感觉到归并排序的执行过程在脑子里“活了”。看动画讲解视频也是同样的效果，但自己运行代码，印象更深。

6. 时间复杂度与空间复杂度分析

归并排序的时间复杂度非常稳定，这是它最大的优点之一。

6.1 时间复杂度：O(n log n)

分析归并排序的时间复杂度，核心是看递归树的层数，以及每一层合并不需要多少工作。

假设数组长度为 n，每次一分为二。递归树的层数大约为 log₂n。例如 n=7，递归深度大概是 3 层；n=1000，深度大约是 10 层。

每一层里，所有合并操作加起来，要处理的总元素数量是 n。虽然拆成了很多小区间，但同一层内每个元素恰好参与一次合并。因此每一层的时间复杂度是 O(n)。

总时间复杂度 = 层数 × 每层工作量 = O(n log n)。

这和冒泡排序、选择排序 O(n²) 相比，在数据量较大时有明显优势。这里给个直观对比：

数据量越大，差距越明显。当 n=10000 时，归并排序的工作量可能只有冒泡排序的三四百分之一。

但要注意，归并排序的时间复杂度不受初始数据顺序影响。这点和快速排序不同：快速排序在数组已经有序时可能退化到 O(n²)，而归并排序无论输入什么顺序，递归结构完全一样，因此时间复杂度始终是 O(n log n)。

6.2 空间复杂度：O(n)

归并排序需要额外的临时数组来存放左右半区。在每一层递归中，merge 函数会申请临时空间，递归深度是 log n，但同一时刻最大占用的临时空间是多少？

关键点：虽然代码看起来在每层递归都会 malloc 空间，但递归的执行是深度优先的。左半部分递归调用结束后，空间先被释放，才会进入右半部分递归。因此某一时刻同时存在的临时空间不是 n × log n，而是 n 级别。

所以归并排序的空间复杂度是 O(n)，不是 O(n log n)。这一点面试中经常被问到，很多人答错。

如果想减少频繁 malloc/free 带来的开销，可以考虑在递归函数外一次性申请一个与原数组等长的临时数组，然后通过下标传进 merge 函数复用。这是工程上常用的优化方式。我们下面会给出这种优化写法。

7. 归并排序优化版本：复用临时数组

递归过程中频繁 malloc 和 free 其实是不必要的，而且有一定的性能开销。更好的做法是：在调用归并排序之前，一次性申请一个临时数组，在整个排序过程中复用。

下面是优化版的完整代码：

// 文件路径：merge_sort_opt.c // 功能：归并排序优化版，复用临时数组，减少内存分配开销 #include <stdio.h> #include <stdlib.h> #include <string.h> // 合并函数：使用外部传入的临时数组 void merge(int arr[], int temp[], 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]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 拷贝左半区剩余元素 while (i <= mid) { temp[k++] = arr[i++]; } // 拷贝右半区剩余元素 while (j <= right) { temp[k++] = arr[j++]; } // 将临时数组中的结果拷贝回原数组 for (i = left; i <= right; i++) { arr[i] = temp[i]; } } // 归并排序递归函数 void mergeSortHelper(int arr[], int temp[], int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSortHelper(arr, temp, left, mid); mergeSortHelper(arr, temp, mid + 1, right); merge(arr, temp, left, mid, right); } // 对外接口：只需要传入数组和长度 void mergeSort(int arr[], int n) { if (n <= 1) { return; } int *temp = (int *)malloc(n * sizeof(int)); if (temp == NULL) { printf("内存分配失败\n"); exit(1); } mergeSortHelper(arr, temp, 0, n - 1); free(temp); } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {5, 2, 9, 1, 5, 6, 3, 8, 7, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("排序前："); printArray(arr, n); mergeSort(arr, n); printf("排序后："); printArray(arr, n); return 0; }

这个版本的改动要点：

1. 临时数组在 mergeSort 接口函数中申请，只分配一次。
2. merge 函数接收 temp 数组作为参数，不再自行 malloc。
3. 对外只暴露 mergeSort(arr, n)，调用者不需要关心 left 和 right 下标，降低了使用门槛。

这种设计比较贴近真实项目的工程习惯：公共接口保持简洁，内部细节封装起来，同时兼顾性能。

8. 归并排序 vs 快速排序，到底选哪个

排序算法里，归并排序和快速排序经常被放在一起比较。很多初学者会问：时间复杂度都是 O(n log n)，它们有什么区别？什么时候用哪个？

归并排序的一个显著优势是稳定。所谓稳定，是指如果数组里有两个相等的元素，排序后它们的相对顺序不会改变。比如有一个对象数组，需要先按姓名排序，再按年龄排序，稳定的排序算法可以保证第二次排序后，年龄相同的人仍然保持姓名的顺序。

另一个优势是归并排序对链表的支持极好。数组的归并排序需要 O(n) 额外空间，但链表归并排序不需要这种额外空间，只需要改变节点的 next 指针。这也是很多链表排序算法选择归并排序而不是快速排序的原因。

快速排序的优势在于空间效率更高。快速排序是原址排序，不需要额外的数组空间，平均情况下表现非常优秀。虽然最坏情况是 O(n²)，但通过随机选择基准值或三数取中法，实际中几乎不会触发最坏情况。正因为快速排序的常数因子小、缓存友好，大多数标准库里的排序实现都使用快速排序思想的变种。

从学习角度讲，我建议你两个都掌握。它们分别代表了分治策略的两种典型应用方向：一个是“先拆后合，合并是重点”（归并排序），一个是“先划分后递归，划分是重点”（快速排序）。理解它们的区别，你对分治思想的理解会上一个台阶。

9. 归并排序常见问题与排查思路

写归并排序的时候，初学者容易遇到一些典型的错误。下面整理成表格，你可以直接对照排查。

如果你遇到排序结果不对，一个非常实用的调试方法：先用一个长度为 5 以内的数组测试，手动在纸上模拟一遍，对比程序和你的模拟过程。归并排序的递归逻辑在小区间上很容易推演，大多数问题都能在这个步骤里暴露出来。

10. 归并排序的实际应用：不只是面试题

有些同学觉得归并排序只是考试和面试用的，实际开发用不上。这个观点不够准确。归并排序的思想在几个真实场景中非常重要。

第一个场景是外部排序。当数据量大到无法全部载入内存时（比如对几十 GB 的文件排序），归并排序是核心方案。做法是先把大文件切成多个能载入内存的小块，对每个小块排序后写回磁盘，然后对这些小块进行多路归并。外排序正是归并排序思想在大数据场景下的延伸。

第二个场景是链表排序。Java 的 Collections.sort() 对对象列表的排序就用到了归并排序思想（TimSort 是归并排序的优化版本）。因为链表不支持随机访问，快速排序在链表上实现麻烦，而归并排序只需要改变指针就能完成。

第三个场景是求逆序对数量。给定一个数组，要求计算有多少对 (i, j) 满足 i < j 且 arr[i] > arr[j]。暴力解法是 O(n²)，而利用归并排序的合并过程，可以在 O(n log n) 时间内完成。原理是：合并两个有序数组时，如果左边数组的某个元素大于右边数组的某个元素，那么左边数组该元素之后的所有元素也都大于右边这个元素，可以一次性统计逆序对数量。

// 文件路径：inversion_count.c // 功能：利用归并排序统计逆序对数量 #include <stdio.h> #include <stdlib.h> long long mergeAndCount(int arr[], int temp[], int left, int mid, int right) { int i = left; int j = mid + 1; int k = left; long long inv_count = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { // arr[i] > arr[j]，说明 arr[i..mid] 都大于 arr[j] inv_count += (mid - i + 1); temp[k++] = arr[j++]; } } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } long long mergeSortAndCount(int arr[], int temp[], int left, int right) { if (left >= right) { return 0; } int mid = left + (right - left) / 2; long long count = 0; count += mergeSortAndCount(arr, temp, left, mid); count += mergeSortAndCount(arr, temp, mid + 1, right); count += mergeAndCount(arr, temp, left, mid, right); return count; } int main() { int arr[] = {1, 20, 6, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int *temp = (int *)malloc(n * sizeof(int)); long long result = mergeSortAndCount(arr, temp, 0, n - 1); printf("逆序对数量：%lld\n", result); free(temp); return 0; }

这个例子很好地说明了：理解归并排序的过程，不只是会背代码，更重要的是能在合并阶段捕捉到额外信息。你能从合并顺序里观察到哪些元素“跨过了”哪些元素，从而快速统计出逆序对数量。

11. 归并排序的稳定性和那些容易踩坑的细节

归并排序是稳定排序，这个结论只在实现正确时成立。关键点在于合并两个有序数组时，遇到相等元素应该怎么办。

正确写法：

if (L[i] <= R[j]) { arr[k] = L[i]; i++; }

当 L[i] 和 R[j] 相等时，我们优先取左半区的元素。由于左半区在原数组中本来就在右半区前面，取出后放进新数组也保持了这个相对顺序，所以稳定性成立。

如果误写成<而不是<=，相等的元素会优先取右半区，相对顺序就颠倒了，稳定排序的性质被破坏。

另外，归并排序的递归深度是 log n 级别，对于长度为 10 万的数组，递归深度大约是 17 层，不会导致栈溢出。但如果数组长度达到百万、千万级别，递归深度也只是 20 到 30 层，仍然可以接受。真正消耗内存的是临时数组的空间，这和使用递归还是迭代无关。

如果面试官问你归并排序能否改成非递归写法，答案是可以的。思路是引入一个 width 变量，从 1 开始翻倍，每次对相邻的 width 长度子数组进行合并，直到整个数组被合并完成。这种方式也叫自底向上的归并排序，避免了递归调用，代码上需要多处理一下数组长度不是 2 的幂的情况。

12. 推荐文章总结与学习路径建议

现在，我们可以把归并排序的学习路径梳理成一条清晰的路线：

第一步，画递归树。拿一个小数组，手动模拟拆分和合并的过程，直到你能不看任何参考资料，独立画出每一层的状态。

第二步，先写 merge 函数。单独构造两个有序数组，验证你的合并代码能否得到正确结果。这一步能通过，归并排序就完成了一半。

第三步，实现完整的递归调用。注意 mid 的计算方法、递归边界条件、左右区间的划分。

第四步，运行演示版代码，观察程序输出与你自己手动模拟的结果是否一致。

第五步，再想三个问题：为什么复杂度是 O(n log n)？为什么空间复杂度是 O(n)？为什么相等元素要用<=而不是<？

把这些步骤做完，你对归并排序的理解就能超过大多数背书式学习者。后面学快速排序时，你也能更清晰地意识到两种分治实现的差异。

归并排序不是那种“看一眼就会”的算法，它的价值恰恰在于它训练的是递归思维和分治思维。这两项能力在二叉树、堆排序、线段树、动态规划等很多后续主题里都会被反复使用。建议先收藏这篇文章，在电脑上打开代码编辑器，把每一段代码亲手敲一遍，再对照过程可视化输出加深理解。代码和思路都在这里了，剩下的就是动手实践。