排序：冒泡 → 归并 → 快排

排 [l, r]  =  排左半边  +  把两个有序的半边合并起来  +  排右半边
              ↑小问题     ↑一步真活                    ↑小问题

三要素（还是第 1 章那三条）：

• 职责：mergeSort(l, r) 把 a[l..r] 排好序
• 边界：l >= r 时只有 0 或 1 个元素，本来就有序
• 递推：先排好两半（信任它们），再合并

唯一真正干活的地方是「合并」，切的时候什么都没做。

合并为什么快？因为两边都已经有序了 —— 各伸一根手指指着开头， 每次比一下，取小的那个往前挪。这就是第 7 章的双指针，O(n) 走完。

第 0 层：1 段，长 n        合并总量 n
第 1 层：2 段，各长 n/2    合并总量 n
第 2 层：4 段，各长 n/4    合并总量 n
...
第 k 层：切到长度 1 为止   一共 log₂n 层

每一层的合并总量都是 n，一共 log₂n 层，所以是 n·log₂n。

n = 100 万时，n² = 一万亿，而 n·log₂n = 两千万 —— 相差五万倍。

归并是「先分后治」，快排是「先治后分」。

快排划分完之后，左边全部 ≤ 基准、右边全部 ≥ 基准，基准本身已经在最终位置上了。 两边各自排好，整体自然有序 —— 不需要任何合并动作。

把「归并」那一栏换成你自己默写的，再点开始。 （想验快排也一样，把代码换成快排即可。）

1. cmp(a, b) 的含义是「a 必须排在 b 前面吗」。

不是「a 比 b 大吗」，也不是「要不要交换」。想不清楚就把这句话念一遍。

2. 两个元素「一样」的时候，必须返回 false。

所以比较相等的情况时，只用 < 和 >，绝对不要用 <= 或 >=。 下一步会让你亲眼看到违反这条的后果。

3. cmp 里不要改动任何外部状态。

sort 内部会以未指定的顺序调用它任意多次。

多关键字的写法是「上一个分不出胜负，才看下一个」：

bool cmp(const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;   // 第一关键字：成绩降序
    return a.id < b.id;                                  // 第二关键字：学号升序
}

注意最后一行不带 if —— 前面都相等了，这里必须给出确定的结论。

写 cmp 时，相等就必须返回 false。比较符只用 < 或 >，绝不用 <= 或 >=。

排序前相等的元素，排序后相对顺序不变。

• std::sort 不保证稳定（内部会到处交换）
• std::stable_sort 保证稳定（代价是需要额外空间，慢一点点）
• 归并排序天生稳定（合并时相等取左边），快排天生不稳定

什么时候必须要稳定？当题目说「成绩相同的按输入顺序输出」时。

不过更保险的做法是：把「输入顺序」也写成一个关键字。

struct Student { int id, score, idx; };   // idx = 输入时的编号
if (a.score != b.score) return a.score > b.score;
return a.idx < b.idx;                     // 用 idx 兜底，就不依赖稳定性了

这样用 sort 也没问题。能不依赖稳定性就不依赖 —— 少一个隐含前提，少一个坑。