归并排序 (Merge Sort)

用柱状动画看归并排序先对半拆分、再按序合并。所有情况保证 O(n log n),代价是 O(n) 额外空间。

算法

数组

大小48
比较中交换/写入枢轴/基准读取已排序
速度50×

比较

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) 临时空间。 排序可视化

常见问题

和快速排序比哪个好?
快排通常更快但可能退化到 O(n²)。归并保证 O(n log n) 且稳定,需要可预期性能时选归并。
为什么需要额外内存?
原地合并会覆盖还没读到的值,需要 O(n) 的临时数组存放合并结果。

其他算法