归并排序:拆分与合并
先把区间一分为二,直到触及单元素基线;再让两个有序队列反复比较队首,把较小者送入 result。
T(n)=2T(n/2)+Θ(n)两个规模约为 n/2 的子问题,加上本层线性归并。
用英文或中文逗号分隔,支持 2~12 个整数。
递归区间
尚未拆分左有序队列
等待拆分完成
右有序队列
result · 逐项增长
当前动作
先拆分根区间。单元素区间天然有序,是递归基线。
本层工作量
等待开始
T(n)=2T(n/2)+Θ(n)
即时判断
合并左队列 [2, 5] 与右队列 [2, 4] 时,第一次比较后应先取哪个 2,才能保持稳定性?