上一页我们说归并排序靠「分」和「合」。合的那一步有个好起点：假设你手里有两副已经排好序的牌，现在要把它们并成一堆仍然有序的牌，你会怎么做？

上一页我们解决了核心问题：两堆已排好的牌能很快合并成一堆。那面对一大堆乱牌呢？先别急着排——把它一分为二，每一半也照此办理，直到手里只剩一张牌：一张牌天然有序。

上半段向下逐层二分到单元素，下半段向上逐层合并回有序数组，一图看尽分与合。

看主算法如何把区间二分、递归、归并三步串成完整排序。

L2 递归基防死循环；L4 二分中点；L7 前两行递归保证归并时两段必有序——这是 merge 能正确工作的前提。

递归拆分数组靠三件事撑住：终止条件、切分点、调用顺序，缺一即崩。

从上往下是调用（拆），从下往上是返回（合），进出各 log₂n 层。

用具体数组走一遍两个有序子序列的合并，看清每次比较与搬运。

双指针逐个比较、谁小谁先走，最后把剩余段整段复制——两堆有序牌真正合并的代码。

三指针分工：i、j 各读一堆，k 负责写回；比较取 <= 保证相等元素相对次序不变，这就是稳定性。

上一页 merge 写完了，但真正动手实现的人，大多栽在边界上：左半区和右半区谁先耗尽？复制的区间是左闭右开还是闭区间？这一页专门收拾这些坑。

指针 i、j、k 的移动轨迹与元素落位关系图

上一页看到双指针一步步移动，但凭什么每步取的就是剩余最小的？就像验收一栋楼，不能只看最后刷得漂亮，要证明每一层砌的时候都没偷工。

双指针过程在两段中都可能先走完，收尾处理是否正确，决定 merge 整体正确性能否闭环。

把每层归并的总代价乘以递归层数，就能推出 O(n log n)。

前面推导出时间复杂度 O(n log n)，但天下没有免费的午餐：merge 阶段需要额外地方存放合并结果。本页回答两个追问——辅助空间到底花在哪，以及相等元素的相对顺序是否会被打乱。

merge 两个已排序子数组时，为什么双指针每次只需比较两段当前的首元素取较小者？

• ✓拆到单元素天然有序，功夫全在合并
• ✓双指针各管一段，逐个取小者保证有序
• ✓相等取左段，稳定性由此而来
• ✓任何输入都是 O(n log n)，代价 O(n) 辅助空间
• ✓递归三要素 + merge = 分治算法的模板

三个开放问题：先自己想一会儿，再看参考答案。