分治与合并：递归与迭代两种写法
基于通用算法套路 · 核于 2026-07
速查
- 自顶向下（递归）：
sort(l,r)→ 取mid→sort(l,mid)+sort(mid+1,r)→merge(l,mid,r)；递归基是l>=r。最直观，递归树自然展开。 - 自底向上（迭代）：步长
width从 1 倍增到n，每轮对所有相邻的[i, i+width-1]与[i+width, i+2*width-1]两段 merge；无需递归，省栈空间。 - 两者等价：复杂度都是 O(n log n) / O(n) 空间 / 稳定；迭代少了递归调用开销，常数略小，但代码更长。
- merge 操作：双指针
i指左段头、j指右段头，每次比较取小者放入结果数组，扫完一段后把另一段剩余整体拷贝——是「分离指针」的典型应用。 - 稳定性关键：merge 比较写成
a[i] <= a[j]取左半（相等也取左半），保证相等元素相对次序不变。 - 临时数组复用：全局开一个长度为 n 的
tmp数组供所有 merge 复用，避免反复分配；这是把空间稳稳压在 O(n) 的工程技巧。 - merge 复杂度：合并两段长度和为 m 的有序段是 O(m)（双指针各最多走 m 步）；递归树每层合并总量 n，共 log₂ n 层 → O(n log n)。
- 「已经有序」优化：merge 前判
a[mid] <= a[mid+1]（左段尾 ≤ 右段头）则跳过合并，最好情况降到 O(n)。 - 自底向上的「尾部不整」：最后一段长度可能不足
width，merge 时要夹紧右边界min(i+2*width-1, n-1)，否则越界。 - 递归 vs 迭代选型：教学/面试默认递归（好写好讲）；追求极致常数或受限环境（禁递归）用迭代；二者结果完全一致。
- 交互演示：归并排序可视化。
一、自顶向下：递归写法
最直观的写法——把排序函数递归定义为「排序 [l, r] 区间」，先切半递归排序两半，再 merge。
function mergeSort(a) {
const tmp = new Array(a.length); // 全局复用，避免反复分配
sort(a, 0, a.length - 1, tmp);
return a;
}
function sort(a, l, r, tmp) {
if (l >= r) return; // 递归基：长度 ≤ 1 天然有序
const mid = (l + r) >> 1; // 对半切（注意位运算向下取整）
sort(a, l, mid, tmp); // 排左半
sort(a, mid + 1, r, tmp); // 排右半
merge(a, l, mid, r, tmp); // 合并两段
}要点：
- 递归基
l >= r：段长 0 或 1 时直接返回，不再切分。 mid = (l+r) >> 1：用位运算向下取整；左段[l, mid]、右段[mid+1, r]，无重叠无遗漏。- 递归树高 ⌈log₂ n⌉：每次对半切，深度由 n 决定，这是 O(log n) 栈空间的来源。
- tmp 全局复用：在入口分配一次，所有递归层共用，避免每次 merge 都
new Array——这是工程上把空间稳稳压在 O(n) 的关键。
二、merge 操作：双指针详解
merge 是归并排序的灵魂——把两个已排序的段（左段 [l, mid]、右段 [mid+1, r]）合并成一个有序段写回原数组。核心是双指针：
function merge(a, l, mid, r, tmp) {
for (let k = l; k <= r; k++) tmp[k] = a[k]; // 1. 拷贝到临时区
let i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) { // 2. 双指针取小（相等取左半 → 稳定）
if (tmp[i] <= tmp[j]) a[k++] = tmp[i++];
else a[k++] = tmp[j++];
}
while (i <= mid) a[k++] = tmp[i++]; // 3. 收尾：左半剩余
while (j <= r) a[k++] = tmp[j++]; // 4. 收尾：右半剩余
}逐步拆解：
- 拷贝到 tmp：先把
[l, r]段整体拷到tmp，merge 时从tmp读、写回a——这样避免「边改边读」的自覆盖问题。 - 双指针取小：
i、j各指向左/右段当前最小元素，比较后取小者写入a[k]并推进。<=取左半是稳定性的关键。 - 收尾：一旦某段耗尽，另一段剩余元素整体拷贝（它们本就有序且都 ≥ 已写入部分）。
复杂度：两段长度和 m = r-l+1，双指针各最多推进 m 步，故 merge 单次 O(m)。这正是递归树每层总工作量 = n 的来源。
常见坑：忘了步骤 1 的拷贝，直接在原数组上双指针合并，会导致左段未被读取的元素被右段覆盖（自覆盖）。
三、自底向上：迭代写法
迭代版不递归，从「步长 1」开始，把相邻的两个长度为 1 的段 merge 成长度为 2 的段；步长翻倍到 2、4、8……直到覆盖整个数组。本质是把递归树「自底向上」地手动展开。
function mergeSortBottomUp(a) {
const n = a.length, tmp = new Array(n);
for (let width = 1; width < n; width <<= 1) { // 步长：1→2→4→…→n
for (let i = 0; i < n; i += 2 * width) { // 每轮处理相邻两段
const mid = i + width - 1; // 左段尾
const r = Math.min(i + 2 * width - 1, n - 1); // 右段尾（夹紧防越界）
if (mid < n - 1) merge(a, i, mid, r, tmp); // 有右段才合并
}
}
return a;
}要点：
width倍增：width <<= 1等价于width *= 2，每轮合并后段长翻倍，共 ⌈log₂ n⌉ 轮。r = min(i+2*width-1, n-1)：最后一段长度可能不足width，右边界要夹紧到n-1，否则 merge 会越界读垃圾。if (mid < n-1)：若左段已是数组末尾（没有右段），无需 merge，直接跳过——因为单段天然有序。- 复用同一个 merge：自顶向下和自底向上用的是完全相同的 merge 函数，只是「组织方式」不同。
与递归版对比：复杂度完全一致（O(n log n) / O(n) 空间 / 稳定），但迭代版省了递归调用开销（函数调用压栈），常数略小；代价是边界处理更繁琐。在禁递归的环境（某些嵌入式系统）或追求极致常数时用迭代。
四、复杂度分析
时间复杂度
T(n) = 2·T(n/2) + O(n) ← 分成两半 + 一次 merge
= 4·T(n/4) + 2·O(n)
...
= n·T(1) + (log₂ n)·O(n) ← log₂ n 层，每层 O(n)
= O(n log n)主定理（Master Theorem）：T(n) = a·T(n/b) + O(nᵈ)，这里 a=2, b=2, d=1，a = bᵈ 落在「情况二」，T(n) = O(n log n)。
三态一致：分治结构固定（递归树形状不随输入变），merge 必扫满，故最好 = 平均 = 最坏 = O(n log n)。
空间复杂度
O(n) 辅助数组（tmp）+ O(log n) 递归栈（自顶向下）≈ O(n)自底向上无递归栈，但仍需 O(n) 辅助数组，所以空间仍是 O(n)。
稳定性
稳定——前提是 merge 比较写成 a[i] <= a[j] 取左半（相等时左半先落位）。
五、工程优化技巧
- 「已有序」跳过合并：merge 前判
if (a[mid] <= a[mid+1]) return;，左段尾 ≤ 右段头时两段本就有序，直接跳过，最好情况降到 O(n)。 - 小数组切回插入排序：段长 ≤ 16（经验阈值）时用插入排序（小数组常数小、无递归开销），这是 Timsort 的核心思想之一。
- 避免整体拷贝：可以让
a和tmp角色在递归层间交替（上一层写 tmp、下一层写 a），省掉每次 merge 的拷贝步骤——但实现复杂，面试一般不要求。 - 链接数组的归并：对索引数组排序（只排下标不搬元素），适合元素本身很大（结构体）的场景。
交互演示
- 归并排序可视化演示 —— 递归树与 merge 合并的双视角
下一步
掌握了两种写法与 merge 细节后，下一步看归并思想的三大应用——逆序对计数（merge 时顺便统计）、海量数据外排序（分块 + 多路归并）、以及 Timsort / 链表归并，见应用：逆序对、外排序与 Timsort。