【分治】归并排序：局部有序到整体有序

核心思想：先把数组不断二分，直到每个子数组只有一个元素；再把相邻的有序子数组两两合并，最终得到完整的有序数组。

1. 问题定义

给定长度为n的数组A[0...n-1]，要求将数组按非递减顺序排列：

A[0]≤A[1]≤⋯≤A[n−1] A[0] \le A[1] \le \cdots \le A[n-1]A[0]≤A[1]≤⋯≤A[n−1]

示例：

输入：[5, 2, 8, 3, 1, 6, 4] 输出：[1, 2, 3, 4, 5, 6, 8]

归并排序使用分治思想，最好、平均和最坏时间复杂度均为O(n log n)。

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

假设已有两个升序数组：

左：[2, 5, 8] 右：[1, 3, 6, 9]

由于两个数组内部已经有序，最小元素一定在两个数组当前未处理部分的首部。每次比较左右首元素，把较小者写入辅助数组。

三个指针

• i：指向左区间尚未处理的第一个元素；
• j：指向右区间尚未处理的第一个元素；
• k：指向辅助数组下一个写入位置。

合并步骤

3. 分治框架

归并排序包含三个阶段：

1. Divide（分解）：从中点把数组分成左右两半；
2. Conquer（解决）：递归地对左右两半排序；
3. Combine（合并）：线性合并两个有序子数组。

当区间长度为0或1时，区间天然有序，可以直接返回。

4. 完整执行过程

以[5, 2, 8, 3, 1, 6, 4]为例。

分解阶段

[5, 2, 8, 3, 1, 6, 4] ├── [5, 2, 8, 3] │ ├── [5, 2] │ │ ├── [5] │ │ └── [2] │ └── [8, 3] │ ├── [8] │ └── [3] └── [1, 6, 4] ├── [1, 6] │ ├── [1] │ └── [6] └── [4]

合并阶段

[5] + [2] -> [2, 5] [8] + [3] -> [3, 8] [2, 5] + [3, 8] -> [2, 3, 5, 8] [1] + [6] -> [1, 6] [1, 6] + [4] -> [1, 4, 6] [2, 3, 5, 8] + [1, 4, 6] -> [1, 2, 3, 4, 5, 6, 8]

递归负责制造“局部有序”，归并负责把两个局部有序区间变成更大的有序区间。

5. 伪代码

MERGE-SORT(A, left, right): if left >= right: return mid = left + (right - left) / 2 MERGE-SORT(A, left, mid) MERGE-SORT(A, mid + 1, right) MERGE(A, left, mid, right) MERGE(A, left, mid, right): i = left j = mid + 1 k = left while 左右区间都还有元素: if A[i] <= A[j]: temp[k] = A[i] i++ else: temp[k] = A[j] j++ k++ 复制左区间剩余元素 复制右区间剩余元素 将 temp[left...right] 写回 A[left...right]

6. C 语言实现

下面的实现只申请一次辅助数组，供整个递归过程复用。

#include<stdio.h>#include<stdlib.h>/** * 合并两个有序区间： * A[left...mid] 和 A[mid+1...right] */staticvoidmerge(int*A,int*temp,intleft,intmid,intright){inti=left;intj=mid+1;intk=left;while(i<=mid&&j<=right){if(A[i]<=A[j]){// 相等时优先取左侧元素，保证稳定性。temp[k++]=A[i++];}else{temp[k++]=A[j++];}}while(i<=mid){temp[k++]=A[i++];}while(j<=right){temp[k++]=A[j++];}for(intp=left;p<=right;p++){A[p]=temp[p];}}staticvoidmergeSortRecursive(int*A,int*temp,intleft,intright){if(left>=right){return;}// 防止 left + right 发生整数溢出。intmid=left+(right-left)/2;mergeSortRecursive(A,temp,left,mid);mergeSortRecursive(A,temp,mid+1,right);merge(A,temp,left,mid,right);}/** * 成功返回 1，内存分配失败或参数无效返回 0。 */intmergeSort(int*A,intn){if(n<=1){return1;}if(A==NULL){return0;}int*temp=malloc((size_t)n*sizeof(int));if(temp==NULL){return0;}mergeSortRecursive(A,temp,0,n-1);free(temp);return1;}

测试代码

staticvoidprintArray(constint*A,intn){for(inti=0;i<n;i++){printf("%d%c",A[i],i==n-1?'\n':' ');}}intmain(void){intarr1[]={5,2,8,3,1,6,4};intarr2[]={1};intarr3[]={9,8,7,6,5};intarr4[]={3,1,3,-2,0};intn1=sizeof(arr1)/sizeof(arr1[0]);intn2=sizeof(arr2)/sizeof(arr2[0]);intn3=sizeof(arr3)/sizeof(arr3[0]);intn4=sizeof(arr4)/sizeof(arr4[0]);if(mergeSort(arr1,n1))printArray(arr1,n1);if(mergeSort(arr2,n2))printArray(arr2,n2);if(mergeSort(arr3,n3))printArray(arr3,n3);if(mergeSort(arr4,n4))printArray(arr4,n4);return0;}

输出：

1 2 3 4 5 6 8 1 5 6 7 8 9 -2 0 1 3 3

7. 正确性说明

可以用数学归纳法证明。

基础情况

区间长度为0或1时，天然有序。

归纳假设

假设所有长度小于n的数组都能被归并排序正确排序。

归纳步骤

对于长度为n的数组：

1. 左右子数组长度都小于n；
2. 根据归纳假设，递归后左右子数组分别有序；
3. merge每次选择两个区间中尚未处理的最小元素；
4. 写入辅助数组的元素始终保持非递减顺序；
5. 合并结束后，整个长度为n的区间有序。

因此归并排序能够正确排序任意长度的数组。

8. 复杂度分析

时间复杂度

递推式为：

T(n)=2T(n/2)+O(n) T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)

• 每层所有合并操作共处理n个元素，工作量为O(n)；
• 每次把规模减半，递归树深度为O(log n)；
• 总时间为O(n) × O(log n) = O(n log n)。

即使数组已经有序，标准归并排序仍会完成全部拆分与合并。

空间复杂度

• 辅助数组：O(n)；
• 递归栈：O(log n)；
• 总体空间复杂度：O(n)。

9. 算法性质

稳定性

若两个元素关键字相同，排序后仍保持原来的相对次序，则算法稳定。

排序前：[3a, 1, 3b] 排序后：[1, 3a, 3b]

合并时使用：

if(A[i]<=A[j])

相等时先取左侧元素，因此保持稳定。如果改为<，可能破坏稳定性。

10. 边界情况

11. 与其他排序算法对比

12. 与逆序对计数的关系

归并排序还可以在合并阶段统计逆序对。

当右侧当前元素小于左侧当前元素时，左区间尚未处理的所有元素都与它构成逆序对，因此可以一次增加：

mid−i+1 mid - i + 1mid−i+1

无序数组 ↓ 不断二分 单元素区间天然有序 ↓ 从下向上两两合并 比较左右当前元素 ├─ 左 <= 右：取左元素 └─ 左 > 右：取右元素 ↓ 复制剩余元素 ↓ 得到更大的有序区间 ↓ 最终数组有序

先递归制造局部有序，再利用线性归并得到整体有序
递推式为T(n)=2T(n/2)+O(n)
所以时间复杂度为O(n log n)
空间复杂度为O(n)