归并排序动画演示
对半分到只剩一个，再两两按序合并回来。
键盘：← → 单步 ·空格 播放/暂停 · R 重置 ·Home/End 到两端
归并排序走的是「先切后合」：区间从中间对半分，一直分到只剩一个元素——那一段天然有序——再两两把有序的段合并成更大的有序段。这一页有两个场景：上面是原数组的柱子，下面是辅助数组，合并时先把这一段抄进辅助数组，再一格一格按序写回原数组。
当前处理的区间用 lo / mid / hi 三个标注框住，mid 单独染成红色，区间外的柱子压暗，已并好的段留着绿色，分治的层次一眼可辨。它的比较次数只跟长度有关，跟数据怎么摆无关，永远 O(n log n)；代价是 O(n) 的辅助空间。它稳定，取左段的那条等号就是稳定性的来源。
归并排序演示怎么用
- 认三色：红色是这一段的分界 mid，绿色是已经并完的段，压暗的柱子在当前的合并之外，不用管它们。
- 跟辅助数组：下面那排格子在抄段时点亮，取走一个就腾空白一格，能看出「读」和「写」是两条线。
- 数比较：计数条只有「比较」与「回填」两项：回填次数固定是 n log n 量级，比较次数随数据在 n/2 到 n 每层之间浮动。
- 看层次：规模给 8 最容易看清完整的三层切分；换 16 会多一层，深度方向上的嵌套关系仍然一致。
常见问题
为什么比较时要用 aux[i] <= aux[j] 取左边？
两段里出现相等的值时，取左边才能保证合并后它们的相对次序跟原来一致。写成 < 就会让右段那个同值元素插到前面去，稳定排序的说法当场就不成立了。
辅助数组能不能省掉？
普通数组上的原地归并写法复杂、常数也大，实际收益不明显。省空间的路线是换结构：链表归并只要改指针，不需要额外数组；外部排序则是一遍遍把大块读进有限的内存里做归并。
它和快速排序该怎么选？
要最坏也有保障、要稳定、要能顺序读写（链表、磁盘、网络流）时选归并；要平均更快、缓存友好、不想多花一份数组时选快排。语言标准库里的稳定排序多半是归并的变体，不稳定排序基本是快排的变体。