01先从一个问题出发
两叠已经排好序的卡片，如何高效合成一叠？
一个具体的例子
[2, 6] 与 [1, 4]，依次选头部较小值 1、2、4、6。
02最直接的办法，为什么慢？
反复找未排序区域中的最小值。
暴力 · O(n²)
每次选择都重新扫描剩余元素，累计平方级比较。
03一步步，推导出优化思路
1
发现可以复用的信息
两个有序数组可以只比较当前头部，用 O(n) 时间合并。
2
建立可维护的状态
把问题不断平分，单元素天然有序。
3
消除重复工作
自底向上合并；每一层总共处理 n 个元素，层数约 log₂ n。
贯穿算法的不变量
合并时，缓冲区已排序，且不大于两个输入区间中尚未取出的元素。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Merge Sort交互演示
STEP 01 / 5035
018
152
227
343
412
560
631
7当前处理已处理 / 已确定未处理
01
从左到右观察数组。橙色表示当前比较，绿色表示已确定的位置。
merge_sort.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
递推 T(n)=2T(n/2)+O(n)，共有 O(log n) 层，每层 O(n)，最好和最坏均为 O(n log n)。
辅助空间
合并缓冲区峰值 O(n)，递归栈 O(log n)，合计 O(n)。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
相等时先选左边
使用 <= 保证跨区间的同值元素仍稳定。
02
半开区间
本实现处理 [left, right)，不要把 right 当作有效下标。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01为什么每层合并是 O(n)？
02相等时先选哪个？
03常规数组归并的额外空间？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。