归并排序
入门稳定 O(n log n) 排序，理解「分」与「合」两个阶段。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void merge(int arr[], int lo, int mid, int hi) {
2 vector<int> temp;
3 int i = lo, j = mid + 1;
4 while (i <= mid && j <= hi) {
5 if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
6 else temp.push_back(arr[j++]);
7 }
8 while (i <= mid) temp.push_back(arr[i++]);
9 while (j <= hi) temp.push_back(arr[j++]);
10 for (int k = 0; k < temp.size(); k++) {
11 arr[lo + k] = temp[k];
12 }
13}
14
15void mergeSort(int arr[], int lo, int hi) {
16 if (lo >= hi) return;
17 int mid = lo + (hi - lo) / 2;
18 mergeSort(arr, lo, mid);
19 mergeSort(arr, mid + 1, hi);
20 merge(arr, lo, mid, hi);
21}
复杂度分析
时间 O(n log n)
空间 O(n)
最优 O(n log n)
最坏 O(n log n)
算法讲解
归并排序先将数组递归地分成两半，直到每个子数组只有一个元素（天然有序）。
合并阶段将两个有序子数组合并为一个有序数组，使用双指针比较。
时间复杂度稳定为 O(n log n)，但需要 O(n) 的额外空间。
稳定排序，适合链表排序和外部排序场景。