故事两叠试卷的合并
期中考试结束，你负责把全班 50 张试卷按分数从高到低排好。手里什么都没有，只能一张一张比较 —— 那就是 O(n²)，50 张要比较上千次，还容易乱。
物理老师路过，说了句：「我先把成绩单交给你，前 25 名和后 25 名各一叠，而且每一叠都已经排好了。」
你立刻发现事情变得极其简单：只要盯着两叠的顶部，每次挑分数高的那张放到新叠上。挑完 50 张，新叠自然就有序了。整个过程只看了 50 次，也就是 O(n)。
可问题来了：物理老师那两叠，又是谁排好的？答案很妙 —— 让两位老师各自去排 25 张，他们也可以用同样的方法，找更小的两叠来合并。一直分下去，每叠只剩 1 张（天然有序），然后一层一层往上合。
自顶向下不停二分，自底向上不停合并 —— 这就是归并排序。
而另一条路更「暴力美」：随便挑一个分数当标杆，比它高的全扔右边、比它低的全扔左边。标杆归位后，左右两边各自再选标杆重新分堆。分得快的时候，几步就能排完 —— 这就是快速排序。
💡 两条路线，两种性格
归并排序：先递归排好两半，再合并。合并需要一块和原数组一样大的辅助空间，但好处是无论数据长什么样，都是严格的 O(n log n)，而且稳定。
快速排序：先按基准值原地分堆，再递归两侧。不需要额外空间（只需递归栈），常数极小，实际跑得最快；但分堆如果不均匀会退化到 O(n²)，而且不稳定。
本讲的目标：两把都亲手写出来，并且知道什么时候该用哪把。