排序是算法界的「试金石」——同一堆数据，各种思想轮番登场。本章两大主角都是分治法（divide-and-conquer）的门面：归并排序与快速排序 🥊。
🪄 归并排序：稳如老狗
四步口诀（分治的标准姿势）：
- 分（divide）：从中点一刀两半；
- 治（conquer）：递归排左半、右半（信它们已有序——递归的信仰之跃 🧘）；
- 合（merge）：两个有序数组，双指针逐个比小，线性时间合并；
- 基（base case）：1 个元素天然有序。
T(n) = 2·T(n/2) + O(n) → O(n log n)
三个金光闪闪的性质：任何输入都 O(n log n)（没有最坏情况陷阱）、稳定排序（相同 key 不换位）、缺点只有一个——O(n) 辅助空间。链表排序的默认首选（合并无需额外空间）。
⚡ 快速排序：激进派
换一个思路：先干「分」的活——选一个基准（pivot），比它小的甩左边，大的甩右边（partition）；递归两边；合并阶段什么都不用做（原地就位）。
- 平均 O(n log n)，且常数因子小、原地排序、缓存友好——实战中常比归并快 2~3 倍；
- 但最坏 O(n²)：每次 pivot 都选中最大/最小值（比如对有序数组取头元素）；
- 解药：随机选 pivot。恶意构造者再也没法针对你——期望 O(n log n) 由数学担保 🎲。C++ 的
std::sort用内省排序（快排+堆排+插排混合），确保任何输入都不掉进 O(n²)。
⚖️ 排序界的「宪法」：下界 Ω(n log n)
所有基于比较的排序，最坏不可能好于 Ω(n log n)（决策树论证：n! 种排列，每次比较提供 1 bit 信息，至少要 log₂(n!) ≈ n log n 次比较）。归并/堆排贴着下界走，已是理论最优——所以别再幻想 O(n) 的比较排序了，除非像计数排序那样「不比较、直接定位」。
🧩 集合与并查集（Union-Find）
判断「这两个元素是否同属一个集合」+「把两个集合并起来」——听起来简单，但需要一个专门结构：
- 森林里每个集合是一棵树，
find就是找根，union把一棵树挂到另一棵上； - 两大优化：按秩合并（矮树挂高树）+ 路径压缩（find 顺手把路上节点全接到根）；
- 效果：n 次操作总共 O(n · α(n))，α 是反阿克曼函数——实际中 α(n) ≤ 4，堪称 O(n)，理论界最神奇的「常数」✨。
应用：最小生成树（Kruskal 靠它判环）、社交网络好友圈合并、迷宫生成。
🎯 快速选择：只要第 k 小
不想全排序，只要第 k 小的元素？快排的 partition 天然给答案：pivot 归位在位置 p——
- p == k：找到了，收工；
- k < p：只递归左边；k > p：只递归右边。
只走一边，期望 O(n)——比排序的 O(n log n) 便宜。求中位数、TopK 问题的基础招式 💪。
🎯 本章通关清单
- [ ] 手工对一个 8 元素数组走一遍归并排序，标出每层合并
- [ ] 说明快排何时退化为 O(n²)，随机化如何救场
- [ ] 解释为什么比较排序不可能优于 Ω(n log n)
- [ ] 用并查集模拟 5 次 union + 3 次 find
下一章，主角换成字符串——以及让无数人闻风丧胆的「动态规划」🧬