排序 · 单步演示
归并排序
先把数组一直对半拆，拆到每段只剩一个数；再把相邻的两段有序段合并：每次比较两段的头，把小的那个写回原数组。
当前操作已就位
步 001 / 055初始数组。归并排序先一路对半拆，拆到只剩一个数，再两两合并成有序段。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
归并排序(lo, hi)：if hi − lo < 1：returnmid ← lo + ⌊(hi − lo) / 2⌋归并排序(lo, mid)；归并排序(mid+1, hi)L ← a[lo..mid]；R ← a[mid+1..hi]；k ← lowhile L、R 都还有数较小的头写到 a[k]（相等取 L）；k ← k+1把没取完的那一段依次写回
变量
| 比较次数 | 0 |
|---|---|
| 交换/写入次数 | 0 |
复杂度
| 最好情况 | O(n log n) |
|---|---|
| 平均情况 | O(n log n) |
| 最坏情况 | O(n log n) |
| 额外空间 | O(n) |
| 稳定性 | 稳定 |
拆分一共 ⌈log₂n⌉ 层，每层合并时每个数都被写回一次，所以每层 O(n)。合并需要额外的 L、R 数组，空间 O(n)。
要点
- 运行时间几乎不受输入顺序影响，这是它和快速排序最大的区别。
- 合并时相等取左边，就能保持稳定。
- 链表排序常用归并：链表合并不需要额外数组。
常见错误
中点写成 (lo + hi) / 2 在一些语言里，lo + hi 可能超出整数范围；写成 lo + (hi − lo) / 2 更稳妥。