一、前言
归并排序是基于分治法的典型排序算法，通过递归将数组拆分为最小单元（单个元素），再通过合并操作将有序子序列逐步组合成完整有序序列。其核心在于分解与合并的协同操作
二、分治法与递归拆分
分治法将原问题分解为若干规模较小但结构相似的子问题，递归求解后再合并子问题的解。归并排序是分治法的直接体现：
拆分：将待排序数组从中间分成左右两半，分别递归排序，直到每个子数组只包含一个元素（单个元素天然有序）。
合并：将两个有序子数组合并为一个有序数组。
整个过程需要两个核心函数：Divide（递归拆分）和Merge（合并两个有序数组）
三、函数设计
Divide函数负责递归拆分数组：
void Divide(int arr[], int left, int right) { int mid = (left + right) / 2; //可能会超int类型存储上限 （left/2 + right/2) if (left < right) { //[left, right] mid //左半边[left, mid] 右半边[mid + 1, right] Divide(arr, left, mid); Divide(arr, mid + 1, right); Merge(arr, left, mid, right); //合并 } }Merge函数负责合并两个有序子数组：
void Merge(int arr[], int left, int mid, int right) { //0.安全判断 //1.申请一个辅助空间brr，长度只要能放下合并的这两个组的所有元素即可 int len = right - left + 1; int* brr = (int*)malloc(sizeof(int) * len); if (brr == NULL) return; //exit(EXIT_FAILURE); //2.申请两个变量i j, 分别指向两个组的第一个元素 int i = left; //左边组开头 int j = mid + 1; //右边组开头 int k = 0; //辅助数组下标 //3.进入while循环，循环条件i,j没有越界（循环合法） while (i <= mid && j <= right) { //4.比较i j指向的两个组的各自第一个元素值 // 谁小谁向下放（brr,相等的话也是下放） if (arr[i] <= arr[j]) brr[k++] = arr[i++]; else brr[k++] = arr[j++]; } //5.当while循环进不去，代表肯定i或者j走完了 //（有一个组的数据被挪动完了），则将另一个组没有挪动完的值同步 while (i <= mid) brr[k++] = arr[i++]; while (j <= right) brr[k++] = arr[j++]; //6.这是两个组的合并结果就在brr里面，最后再将brr的数据同步给arr for (k = 0; k < len; k++) { arr[left + k] = brr[k]; } // 释放临时空间 free(brr); brr = NULL; }MergeSort函数对外接口
void MergeSort(int arr[], int len) { //执行递归分函数 Divide(arr, 0, len - 1); }四、手算模拟
以数组[5, 3, 8, 4, 2]为例：
拆分阶段：
- 第一层拆分：
[5,3,8]和[4,2] - 第二层拆分：
[5,3]、[8]和[4]、[2] - 第三层拆分：
[5]、[3]
- 第一层拆分：
合并阶段：
- 合并
[5]和[3]得到[3,5] - 合并
[3,5]和[8]得到[3,5,8] - 合并
[4]和[2]得到[2,4] - 最终合并
[3,5,8]和[2,4]得到[2,3,4,5,8]
- 合并
五、复杂度分析
- 时间复杂度：所有情况均为O(n log n)。每次递归将问题规模减半（log n层），每层需O(n)时间合并。
- 空间复杂度：O(n)用于辅助数组。
- 稳定性：稳定（由于合并时对相等元素优先取左子数组元素，算法是稳定的）
六、优缺点对比
- 优点：
- 时间复杂度稳定为O(n log n)，不受输入数据分布影响。
- 稳定排序，适合需要保持原始顺序的场景。
- 缺点：
- 需要额外O(n)空间，不适合内存严格受限的环境。
- 对比O(n²)排序（如冒泡排序）：
- 归并排序在大规模数据下效率显著更高，但小规模数据可能因递归开销反而更慢。
下次我们将讲解另一种分治排序——快速排序，它采用不同的拆分策略（按基准元素划分），且可以做到原地排序。敬请期待
