归并排序用于对一组线性存储的数据进行排序，是一种基于分治法的经典排序算法。
归并排序的核心思想是将一个大数组分解成两个小数组去解决。然后递归地排序这两个小数组，最后将排序好的小数组合并成一个大数组。归并排序的效率来自于它合并两个已排序数组的能力——合并操作只需线性时间即可完成。
归并排序的三个步骤：
考虑数组 [3, 1, 4, 1, 5, 9, 2, 6] 的排序过程：
分解阶段：
合并阶段：
以下是归并排序的完整实现，包含合并函数和递归排序函数：
1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// 合并两个有序数组段的函数
11void merge(int a[], int left, int mid, int right) {
12 int t[105] = {0}; // 创建一个临时数组用于存储合并后的有序序列
13 int lp = left; // lp是左半部分的起始索引
14 int rp = mid + 1; // rp是右半部分的起始索引
15 int si = left; // si是用于追踪当前要插入元素到临时数组t的索引
16
17 // 遍历左右两部分，直到一个达到终点
18 while (si <= right) {
19 // 如果左半部分已完全处理完毕，或者右半部分当前元素小于左半部分当前元素
20 if (lp > mid || (rp <= right && a[lp] > a[rp])) {
21 t[si] = a[rp]; // 将右半部分当前元素拷贝到临时数组
22 rp++; // 移动右半部分的索引
23 }
24 else {
25 t[si] = a[lp]; // 否则，将左半部分当前元素拷贝到临时数组
26 lp++; // 移动左半部分的索引
27 }
28 si++; // 移动临时数组的索引
29 }
30
31 // 将临时数组中排序后的元素拷贝回原数组a
32 for (int i = left; i <= right; i++) {
33 a[i] = t[i];
34 }
35}
36
37// 归并排序的递归实现
38void merge_sort(int a[], int left, int right) {
39 if (right <= left) {
40 return; // 如果当前数组段的长度为1或0，直接返回
41 }
42 int mid = (left + right) / 2; // 找到中点，将数组分成两半
43 merge_sort(a, left, mid); // 递归排序左半部分
44 merge_sort(a, mid + 1, right); // 递归排序右半部分
45 merge(a, left, mid, right); // 合并两个有序的半部分
46}
47
48int main() {
49 int n = 0;
50 cin >> n;
51 for (int i = 0; i < n; i++) {
52 cin >> a[i];
53 }
54 merge_sort(a, 0, n - 1);
55 for (int i = 0; i < n; i++) {
56 cout << a[i] << ' ';
57 }
58 cout << endl;
59 return 0;
60}以数组 [5, 2, 8, 1, 9, 3] 为例，展示完整的归并排序递归分解和合并过程：
第一阶段：递归分解
1merge_sort([5, 2, 8, 1, 9, 3], 0, 5)
2├── merge_sort([5, 2, 8], 0, 2) ← 左半部分
3│ ├── merge_sort([5, 2], 0, 1)
4│ │ ├── merge_sort([5], 0, 0) ← 基案，直接返回
5│ │ └── merge_sort([2], 1, 1) ← 基案，直接返回
6│ │ → merge([5], [2]) = [2, 5] ★ 合并
7│ └── merge_sort([8], 2, 2) ← 基案，直接返回
8│ → merge([2, 5], [8]) = [2, 5, 8] ★ 合并
9└── merge_sort([1, 9, 3], 3, 5) ← 右半部分
10 ├── merge_sort([1, 9], 3, 4)
11 │ ├── merge_sort([1], 3, 3) ← 基案，直接返回
12 │ └── merge_sort([9], 4, 4) ← 基案，直接返回
13 │ → merge([1], [9]) = [1, 9] ★ 合并
14 └── merge_sort([3], 5, 5) ← 基案，直接返回
15 → merge([1, 9], [3]) = [1, 3, 9] ★ 合并
16→ merge([2, 5, 8], [1, 3, 9]) = [1, 2, 3, 5, 8, 9] ★ 最终合并第二阶段：详细展示最后一次合并过程
合并 [2, 5, 8] 和 [1, 3, 9]：
| 步骤 | 比较 | 选取 | 结果数组 | 左指针lp | 右指针rp |
|---|---|---|---|---|---|
| 1 | 2 vs 1 | 取右边的1 | [1] | 0 | 1 |
| 2 | 2 vs 3 | 取左边的2 | [1,2] | 1 | 1 |
| 3 | 5 vs 3 | 取右边的3 | [1,2,3] | 1 | 2 |
| 4 | 5 vs 9 | 取左边的5 | [1,2,3,5] | 2 | 2 |
| 5 | 8 vs 9 | 取左边的8 | [1,2,3,5,8] | 3(越界) | 2 |
| 6 | 左边用完 | 取右边的9 | [1,2,3,5,8,9] | - | 3(越界) |
归并排序的复杂度和特性如下：
使用归并排序解决问题时：
t[105] 应根据实际数据规模调整。a[lp] 和 a[rp] 之前，必须先检查 lp 和 rp 是否已经越界。如果一边已经用完，应该直接取另一边的元素。left 拷贝到 right，不是从 0 到 right-left。mid = left + (right - left) / 2 而非 mid = (left + right) / 2，后者在 left 和 right 很大时可能整数溢出。