归并排序
入门稳定 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)