用柱状动画看归并排序先对半拆分、再按序合并。所有情况保证 O(n log n),代价是 O(n) 额外空间。
算法
数组
比较
0
交换/写入
0
步数
0/535
读取
0
辅助内存
0
递归深度
1/1
放慢速度,用「单步」对照伪代码高亮和柱条颜色。
伪代码
mergeSort(lo, hi)
mid ← (lo+hi)/2
mergeSort(lo,mid) mergeSort(mid+1,hi)
while left & right remain
a[k] ← smaller of the two fronts
copy merged run back
时间复杂度
| 最好 | O(n log n) |
|---|---|
| 平均 | O(n log n) |
| 最坏 | O(n log n) |
| 空间 | O(n) |
| 稳定 | 是 |
归并排序是分治法的代表:递归地把数组对半拆到单个元素,再比较两个有序段的首元素,取较小者依次合并。
拆分深度 log n,每层合并处理全部 n 个元素,因此最好/平均/最坏都是 O(n log n)。稳定排序,但需要 O(n) 临时空间。 排序可视化