归并排序是”分而治之”的经典示例：把数组对半切直到每段只剩一个元素，然后两两合并回去——合并时利用”两段已经有序”这个事实，做一次线性扫描就能得到合并后的有序段。
三步思路
- 分：把
[lo, hi)切成[lo, mid)和[mid, hi) - 治：递归对两半排序
- 并：用辅助数组
aux暂存当前段，两个指针轮流取较小的，写回原数组
复杂度
- 时间：O(n log n)（无论输入如何，递归深度 log n、每层 O(n) 合并）
- 空间：O(n)（辅助数组）
- 稳定：是（合并时使用
<=，相等元素保持先后顺序）
试试看
上方输入框可以改数组、打乱、生成随机。归并排序处理重复值特别稳——相等元素的相对顺序保持不变，可以试 4, 2, 4, 2, 1 看动画。
在动画里看什么
- 当前正在合并的区间在柱状图里高亮
- 下方”辅助”行显示从原数组复制出来的副本
- 蓝框标出”下一个要写入的辅助下标”