把大问题一分为二，各自解决，再合并结果——分而治之。归并排序和快速排序都是分治的经典应用。
分治（Divide and Conquer）由三个步骤组成：
分治的威力在于：把一个 O(n²) 的问题，通过"分成两半、各自解决"变成 O(n log n)。每次对半切，只需要 log₂n 层，每层合并的总工作量是 O(n)，整体就是 O(n log n)。
归并排序是最标准的分治算法：
以数组 [5, 2, 8, 1, 9, 3] 为例，完整展示分裂和合并的过程：
| 1 | int a[MAXN], tmp[MAXN]; // tmp 是合并时的临时数组 |
| 2 | |
| 3 | void merge_sort(int l, int r) { |
| 4 | if (l >= r) return; // 边界：只有 1 个元素，无需排序 |
| 5 | |
| 6 | int mid = (l + r) / 2; |
| 7 | merge_sort(l, mid); // ① 分：递归排左半段 |
| 8 | merge_sort(mid+1, r); // ① 分：递归排右半段 |
| 9 | |
| 10 | // ③ 合：双指针合并两段有序数组 |
| 11 | int i = l, j = mid+1, k = l; |
| 12 | while (i <= mid && j <= r) |
| 13 | tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; |
| 14 | while (i <= mid) tmp[k++] = a[i++]; // 左段剩余 |
| 15 | while (j <= r) tmp[k++] = a[j++]; // 右段剩余 |
| 16 | for (int x = l; x <= r; x++) a[x] = tmp[x]; // 写回原数组 |
| 17 | } |
| 18 | |
| 19 | // 调用方式 |
| 20 | merge_sort(1, n); // 对 a[1..n] 排序 |
i、j 分别指向左段和右段的当前位置，每次把更小的那个放进 tmp，直到某段用完后把另一段剩余元素直接追加进去。合并操作是线性的 O(n)，这是归并排序效率的保证。
快速排序也是分治，但与归并排序"先分后合"的思路相反——它先处理再递归：选一个基准值（pivot），把数组分成"比它小的"和"比它大的"两部分，再分别递归。合并步骤几乎不需要额外工作。
pivot（红色）经过一次 partition 后，落在它最终应该在的位置上——左边都比它小，右边都比它大。此后只需递归处理左右两段，不需要额外的合并步骤。
| 1 | void quick_sort(int l, int r) { |
| 2 | if (l >= r) return; |
| 3 | int pivot = a[(l+r)/2]; // 取中间元素作基准（降低最坏情况概率） |
| 4 | int i = l - 1, j = r + 1; |
| 5 | while (i < j) { |
| 6 | do i++; while (a[i] < pivot); // 找左边第一个 ≥ pivot 的 |
| 7 | do j--; while (a[j] > pivot); // 找右边第一个 ≤ pivot 的 |
| 8 | if (i < j) swap(a[i], a[j]); // 交换，使左小右大 |
| 9 | } |
| 10 | quick_sort(l, j); // 递归左段 |
| 11 | quick_sort(j+1, r); // 递归右段 |
| 12 | } |
逆序对是指数组中满足 i < j 但 a[i] > a[j] 的数对。暴力枚举所有对是 O(n²)，利用归并排序的合并过程可以在 O(n log n) 内统计完——合并时，每次右段的元素比左段当前元素小，说明它与左段剩余元素构成若干逆序对。
| 1 | long long ans = 0; |
| 2 | |
| 3 | void merge_sort(int l, int r) { |
| 4 | if (l >= r) return; |
| 5 | int mid = (l + r) / 2; |
| 6 | merge_sort(l, mid); |
| 7 | merge_sort(mid+1, r); |
| 8 | int i = l, j = mid+1, k = l; |
| 9 | while (i <= mid && j <= r) { |
| 10 | if (a[i] <= a[j]) tmp[k++] = a[i++]; |
| 11 | else { |
| 12 | ans += mid - i + 1; // 左段 i..mid 都比 a[j] 大，都构成逆序对 |
| 13 | tmp[k++] = a[j++]; |
| 14 | } |
| 15 | } |
| 16 | while (i <= mid) tmp[k++] = a[i++]; |
| 17 | while (j <= r) tmp[k++] = a[j++]; |
| 18 | for (int x=l;x<=r;x++) a[x]=tmp[x]; |
| 19 | } |
a[j] 比左段 a[i] 小时，左段从 i 到 mid 的所有元素都与 a[j] 构成逆序对，一次性加上 mid - i + 1。
| 对比项 | 归并排序 | 快速排序 |
|---|---|---|
| 分的方式 | 从中间对半切，左右大小相等 | 按 pivot 值分，两侧大小不定 |
| 关键步骤 | 合并（Combine）——双指针合并 | 划分（Partition）——双指针交换 |
| 时间复杂度 | O(n log n) 稳定 | 平均 O(n log n)，最坏 O(n²) |
| 空间复杂度 | O(n)，需要临时数组 | O(log n) 递归栈，原地排序 |
| 稳定性 | 稳定（相等元素相对顺序不变） | 不稳定 |
| 竞赛适用 | 需要稳定排序、统计逆序对时用 | 通用排序首选（或直接用 sort） |
sort，但归并统计逆序对是必须手写的经典题型。