自顶向下归并 Top-Down Merge Sort
归并排序 · 递归分治 · 与迭代版对照
归并排序的另一种写法
站内的归并排序页走的是自底向上路线：不递归，段宽从 1 开始一轮轮翻倍合并。本页是同一算法的另一种经典写法——自顶向下（递归分治）：sort(lo, hi) 把区间对半劈开，先递归排好左半、再递归排好右半，回程时把两个有序半段合并成一段。递归到单个元素天然有序，就是分治的「底」。
递归怎么走：看调用栈
递归的执行轨迹就是一棵分治树，而机器执行它靠的是调用栈。下面播放器里右侧的栈轨显示的正是当前的递归调用链：压栈 = 下钻（区间对半、进入子问题），栈顶 = 正在处理的区间，合并完成后弹栈 = 返回上一层。温度计式的 temp 轨（同归并排序页）则展示每次合并：两段比较取小、依次写入 temp、整段拷回。
下面固定 8 个数 [6, 3, 8, 1, 9, 2, 7, 4]。点「下一步」：看栈先压到 [0,7] → [0,3] → [0,1] 三层深，才做第一次合并 [6],[3] → [3,6]；随后逐层回程合并、栈逐层收缩，最后合并 [1,3,6,8] 与 [2,4,7,9] 得到全序。
区间栈 · 每格 = 一段待排序子数组 a[lo..hi]（栈顶先弹出分区）
a[0..7]
下钻 [0,7]：对半为 [0,3] 与 [4,7]
1function mergeSort(a: number[], lo = 0, hi = a.length - 1): number[] {
2 if (lo >= hi) return a;
3 const mid = (lo + hi) >> 1;
4 mergeSort(a, lo, mid);
5 mergeSort(a, mid + 1, hi);
6 const temp: number[] = [];
7 let i = lo, j = mid + 1;
8 while (i <= mid && j <= hi) {
9 if (a[i] <= a[j]) {
10 temp.push(a[i++]);
11 } else {
12 temp.push(a[j++]);
13 }
14 }
15 while (i <= mid) temp.push(a[i++]);
16 while (j <= hi) temp.push(a[j++]);
17 for (let k = 0; k < temp.length; k++) a[lo + k] = temp[k];
18 return a;
19}
n8
深度1
lo0
mid3
hi7
i-
j-
k-
a[i]-
a[j]-
writeCount0
1 / 63
复杂度与两种写法的取舍
与自底向上完全一致：时间 O(n log n)（每层合并共 O(n)、层数 log n）、额外空间 O(n)（temp）、稳定。差别在驱动方式：递归版代码更贴近「分治」的思维模型，是教科书与面试的标准版本；迭代版省去递归调用开销、也不吃栈深，工程里两者都常见。
自顶向下（本页）：递归下钻对半分，回程逐层合并——分治思想的标准载体，配调用栈看最清楚。
自底向上（归并排序页）：段宽 1→2→4→8 迭代翻倍——同一个 merge，不递归、免栈深。
两页的合并过程一模一样，对照着单步走一遍，「归并」就吃透了。
自底向上（归并排序页）：段宽 1→2→4→8 迭代翻倍——同一个 merge，不递归、免栈深。
两页的合并过程一模一样，对照着单步走一遍，「归并」就吃透了。
递归 + 合并的组合还会在 TimSort（Python/Java 实际使用的排序）里再升级——识别天然有序段再归并。那是排序线后面的进阶篇。