归并排序:拆分与合并

先把区间一分为二,直到触及单元素基线;再让两个有序队列反复比较队首,把较小者送入 result。

T(n)=2T(n/2)+Θ(n)两个规模约为 n/2 的子问题,加上本层线性归并。
用英文或中文逗号分隔,支持 2~12 个整数。

递归区间

尚未拆分

左有序队列

等待拆分完成

右有序队列

result · 逐项增长

当前动作

先拆分根区间。单元素区间天然有序,是递归基线。

本层工作量

等待开始

T(n)=2T(n/2)+Θ(n)

即时判断

合并左队列 [2, 5] 与右队列 [2, 4] 时,第一次比较后应先取哪个 2,才能保持稳定性?