# 排序算法专题（下）|算法篇

> 本文系统讲解归并排序、堆排序等高级排序算法，深入分析分治思想在排序中的应用，配合详细的排序过程演示和代码实现，帮助读者全面掌握高效排序算法的原理、实现方法及面试常见考点，提升算法能力。

- 原文：https://feinterview.poetries.top/docs/algorithm/algorithm-interview/20-%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%EF%BC%88%E4%B8%8B%EF%BC%89
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2026.10.08
- 可见范围：免费部分

---

## 认识“分治”思想

- 分治三步：拆成同类小问题 → 分别解决 → 合并结果
- 递归要有基线（比如长度 `≤ 1` 直接返回），每次拆分规模必须严格变小
- 合并是关键，只拆不合等于没做
- 归并排序：拆分简单、合并费力；快速排序：拆分（分区）费力、合并不用做
- 递归太深可以改成自底向上迭代，分治思想不变

**分治就是把大问题拆成几个同样结构的小问题，各自解决，再把结果合起来。** 好比一个班的试卷让一个人改太慢，拆给四个组各改一摞，最后汇总分数。排序里的两个经典例子：归并排序拆分很简单，从中间切开就行，力气花在合并上；快速排序正好反过来，力气花在分区上，分完左右各自排好就天然有序，不用合并。写递归时我会先确认两件事：基线是什么，每次拆分规模是不是一定变小。

本节我们要学习的两个排序算法都是对“分治”思想的应用。
“分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。

> 利用分治思想解决问题，我们一般分三步走：

- 分解子问题
- 求解每个子问题
- 合并子问题的解，得出大问题的解

下面我们一起来看看分治思想是如何帮助我们提升排序算法效率的。

- **数组切两半，各自排好后直接拼起来，算分治吗？**

  不算完整的分治，少了合并。`[3, 4]` 和 `[1, 2]` 各自有序，直接拼是 `[3, 4, 1, 2]`，还是乱的，得用双指针合并。

- **写一个分治排序的递归函数，入参、返回值和终止条件怎么定？**

  入参是数组或 `[lo, hi)` 区间，返回有序结果，长度 `≤ 1` 直接返回。区间开闭全程统一用左闭右开，切分点 `mid = (lo + hi) >> 1`，不会漏也不会重叠。

- **数据太大，递归太深栈溢出，要放弃分治吗？**

  不用，换实现方式就行。归并可以写成自底向上：先两两合并长度 `1` 的段，再合并长度 `2` 的，以此类推。其实归并递归深度只有 `log n`，`100` 万条才 `20` 层，真栈溢出多半是切分写错导致不收敛。

- **线上排序结果偶尔少元素，叶子节点都没问题，先查哪？**

  查合并。最常见的是一侧耗尽后忘了把另一侧剩余部分接上。加个断言：合并结果长度等于左右长度之和。

- **快排和归并都是分治，区别在哪？**

  归并先拆后合，排序发生在合并阶段，稳定、时间稳定 `O(n log n)`，但要 `O(n)` 辅助空间。快排先分区再递归，原地排，平均 `O(n log n)`，最坏 `O(n²)`，不稳定。

## 归并排序

- 一直对半切到单个元素，再两两用双指针合并成有序段
- 递归只负责拆，真正的排序发生在合并
- 每层合并处理 `n` 个元素，共 `log n` 层 → 稳定 `O(n log n)`，不分好坏情况
- 数组版要 `O(n)` 辅助空间；相等时先取左边才稳定（`<=` 而不是 `<`）
- 适合链表排序、外部排序、要求稳定的场景

**归并排序就是先把数组一直对半切到只剩一个元素，再两两合并，合并时用双指针保证每次合出来都是有序的。** 单个元素天然有序，所以整件事就变成了反复合并两个有序数组，这一步是线性的。一共 `log n` 层，每层合并所有 `n` 个元素，所以不管输入什么样都是 `O(n log n)`，这是它比快排稳的地方。代价是数组版要 `O(n)` 的额外空间。合并时两边相等要先取左边，写成 `<=`，不然就不稳定了。
> **回答参考：**“归并的核心是两个有序段线性合并。递归只负责划分，真正的排序发生在合并阶段。”

- **有人说递归返回时数组自然就有序了，错在哪？**

  递归只是把数组拆小再拿回两个有序段，真正让整体有序的是合并那一步。去掉合并直接拼接，跨段的元素还是乱的。

- **合并两个有序数组，代码怎么写才好检查？**

  两个指针各指一边，每次取较小的放进结果，谁被取了谁的指针往后走。一边耗尽后把另一边剩下的 `concat` 上去。最后断言结果长度等于两边之和。

- **换成链表排序，归并有什么不一样？**

  合并直接改 `next` 指针，不需要额外数组，空间降到 `O(log n)`（递归栈）。找中点用快慢指针，切开时记得把前半段尾节点的 `next` 置 `null`，不然会成环。

- **文件太大内存装不下，怎么用归并排？**

  外部排序：先切成能装进内存的块，每块内部排好写回磁盘，再同时打开这些有序块做多路归并，每路只读当前最小值。多路归并时用一个小顶堆挑最小值。

- **为什么 `V8` 的 `sort` 用 `TimSort` 而不是快排？**

  `TimSort` 是归并加插入的混合，稳定，而且对部分有序的数据很快，真实业务数据大多是这样。`V8` 从 `7.0` 起换成它，`ES2019` 也把 `sort` 稳定写进了规范，之前的快排版本对长数组是不稳定的。

### 思路分析

- 分解：从中间切两半，一直切到每段只有一个元素
- 求解 + 合并：单元素天然有序，两两合并成更大的有序段
- 合并时结果前缀一直有序，装的是两边已消费的最小元素
- 一侧耗尽后另一侧剩余直接接上，它本身有序
- 切分必须让规模严格变小，`mid = Math.floor(len / 2)` 对 `len ≥ 2` 两边都非空

**归并排序把分治三步填得很具体：从中间切两半一直切到单元素，然后从最小的段开始两两合并，合到原长度就排完了。** 单元素不用排，所以排序问题就变成了「合并两个有序数组」，这个用双指针一遍就能搞定。合并过程中，结果数组里放进去的部分一直是有序的，因为每次都取两边当前最小的。最后一定要把没取完的那一侧接上，这是最常见的漏写点。
```js
function merge(a, b) {
  const res = []
  let i = 0, j = 0
  while (i < a.length && j < b.length) {
    res.push(a[i] <= b[j] ? a[i++] : b[j++]) // <= 保证稳定
  }
  return res.concat(a.slice(i), b.slice(j)) // 剩余部分直接接上
}
merge([3, 7], [1, 5, 9]) // [1, 3, 5, 7, 9]
```

> 归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：

- 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
- 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。
合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组

- **基线改成切到空数组才停，会出什么事？**

  长度为 `1` 时 `mid = 0`，切出来左边空、右边还是长度 `1`，右边永远切不小，无限递归直到栈溢出。基线要写 `len <= 1`。

- **怎么证明合并没漏元素？**

  循环结束时至少有一边耗尽，另一边剩下的必须全部接上。再加断言 `res.length === a.length + b.length`，漏了马上能发现。

- **要求相等记录保持原顺序，合并时怎么比？**

  相等时取左边，用 `a[i] <= b[j]`。左段的元素在原数组里本来就靠前，每一层都这么取，整体就稳定。教程里的代码用的是 `<`，相等时先取右边，结果数值对但不稳定。

- **长度正常但局部逆序，单元素和两元素用例都过了，怎么查？**

  每层打印左右输入和合并输出。输入就无序，问题在更深一层；输入有序、输出乱了，就查比较方向和指针推进。

- **左右排好后，比一下 `left` 最后一个和 `right` 第一个，能省掉合并吗？**

  能，`left[left.length - 1] <= right[0]` 时直接拼接就行，这是个常见优化，对有序输入能明显提速。但一般情况还是得合并，它只是个快速通道。

### 真实排序过程演示

- `[8,7,6,5,4,3,2,1]` 切三次到单元素：`8 → 4 → 2 → 1`
- 合并三次：`[7,8 | 5,6 | 3,4 | 1,2]` → `[5,6,7,8 | 1,2,3,4]` → `[1..8]`
- `mergeSort` 递归拆分：`len <= 1` 返回，`slice(0, mid)` 和 `slice(mid)` 各自递归
- `mergeArr` 双指针合并，一侧耗尽后 `concat` 另一侧剩余
- 比较写 `arr1[i] < arr2[j]` 相等时先取右边，不稳定，要稳定写 `<=`；每层 `slice` 会产生新数组，总空间 `O(n)`

**这个例子把归并的过程摊得很清楚：`8` 个元素切三次到单元素，再合并三次回到 `8` 个，正好对应 `log 8 = 3` 层。** 代码分两块，`mergeSort` 负责拆，到长度 `≤ 1` 就返回；`mergeArr` 负责合并两个有序数组，用双指针一边取较小的，一边耗尽就把另一边剩下的接上。有个细节：比较写成 `arr1[i] < arr2[j]` 的话，相等时会先取右边，数值没问题但不稳定，要保稳定就写 `<=`。

下面我们基于归并排序的思路，尝试对以下数组进行排序：

```js
[8, 7, 6, 5, 4, 3, 2, 1]
```

- 首先重复地分割数组，整个分割过程如下：
- 首次分割，将数组整个对半分：

```
[8, 7, 6, 5,| 4, 3, 2, 1]
```

> 二次分割，将分割出的左右两个子数组各自对半分：

```
[8, 7,| 6, 5,| 4, 3,| 2, 1]
```

> 三次分割，四个子数组各自对半分后，每个子数组内都只有一个元素了：

```
[8,| 7,| 6,| 5,| 4,| 3,| 2,| 1]
```

> 接下来开始尝试解决每个子问题。将规模为1的子数组两两合并为规模为2的子数组，合并时确保有序，我们会得到这样的结果：

```
[7, 8,| 5, 6,| 3, 4,| 1, 2]
```

> 继续将规模为2的按照有序原则合并为规模为4的子数组：

```
[5, 6, 7, 8,| 1, 2, 3, 4]
```

> 最后将规模为4的子数组合并为规模为8的数组：

```
[1, 2, 3, 4, 5, 6, 7, 8]
```

整个数组就完全有序了。

编码实现

> 通过上面的讲解，我们可以总结出归并排序中的两个主要动作：

- 分割
- 合并

> 这两个动作是紧密关联的，分割是将大数组反复分解为一个一个的原子项，合并是将原子项反复地组装回原有的大数组。整个过程符合两个特征：

- 重复（令人想到递归或迭代）
- 有去有回（令人想到回溯，进而明确递归这条路）

因此，归并排序在实现上依托的就是递归思想。

> 除此之外，这里还涉及到另一个小小的知识点——两个有序数组的合并。合并有序数组是咱们在第 7 节讲过的一道真题，涉及到双指针法。此处强烈建议印象模糊的同学回头复习一下完整的解题思路。

编码实现

```js
function mergeSort(arr) {
    const len = arr.length
    // 处理边界情况
    if(len <= 1) {
        return arr
    }
    // 计算分割点
    const mid = Math.floor(len / 2)
    // 递归分割左子数组，然后合并为有序数组
    const leftArr = mergeSort(arr.slice(0, mid))
    // 递归分割右子数组，然后合并为有序数组
    const rightArr = mergeSort(arr.slice(mid,len))
    // 合并左右两个有序数组
    arr = mergeArr(leftArr, rightArr)
    // 返回合并后的结果
    return arr
}

function mergeArr(arr1, arr2) {
    // 初始化两个指针，分别指向 arr1 和 arr2
    let i = 0, j = 0
    // 初始化结果数组
    const res = []
    // 缓存arr1的长度
    const len1 = arr1.length
    // 缓存arr2的长度
    const len2 = arr2.length
    // 合并两个子数组
    while(i < len1 && j < len2) {
        if(arr1[i] < arr2[j]) {
            res.push(arr1[i])
            i++
        } else {
            res.push(arr2[j])
            j++
        }
    }
    // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
    if(i<len1) {
        return res.concat(arr1.slice(i))
    } else {
        return res.concat(arr2.slice(j))
    }
}
```

- **单元素切完直接原样拼回去，会得到什么？**

  还是 `[8,7,6,5,4,3,2,1]`，原样拼回只是撤销了拆分。顺序是在每一层合并时按大小重排出来的，比如 `8`、`7` 合成 `[7,8]`。

- **`len <= 1` 和 `Math.floor(len / 2)` 为什么要一起看？**

  前者保证最小规模能返回，后者保证 `len ≥ 2` 时左右两段都非空、都比原来小。两个一起才能保证递归收敛，奇数长度也能正确切开，比如 `5` 切成 `2` 和 `3`。

- **大量重复值时，`arr1[i] < arr2[j]` 有什么副作用？**

  相等时走 `else` 先取右边，右段的元素跑到左段相等元素前面，不稳定。按金额排订单时，同金额的顺序会被打乱。改成 `<=`。

- **大数组报 `Maximum call stack size exceeded`，先查哪？**

  归并的递归深度只有 `log n`，`100` 万才 `20` 层，正常不会爆栈。所以先查基线有没有命中、`slice` 的范围是不是写成了原数组本身，基本都是切分写错导致无限递归。

- **想用原地合并省掉结果数组，值得吗？**

  一般不值。原地合并要处理还没读的数据被覆盖，要么大量搬移变成 `O(n²)`，要么用很复杂的算法。工程上常见的折中是只开一个 `O(n)` 的辅助数组复用到底，避免每层 `slice` 反复分配。

### 编码复盘——归并排序的时间复杂度分析

- 一句话：层数 `log n` × 每层总工作量 `n` = `O(n log n)`
- 同一层有很多次 `mergeArr`，但它们加起来刚好把 `n` 个元素各碰一次
- 合并是双指针，每个元素只进结果数组一次 → 单次合并 `O(m)`
- 有序、逆序、乱序输入都一样是 `O(n log n)`，归并对输入分布不敏感
- 空间：辅助数组 `O(n)` + 递归栈 `O(log n)`；示例里的 `slice` 还会额外复制

**归并排序的时间复杂度是 `O(n log n)`，不管输入长什么样都是这个数。** 拆分是对半砍，砍到单元素一共 `log n` 层；每一层虽然有好几次合并，但这些合并加起来正好把 `n` 个元素各处理一次，所以每层是 `O(n)`。两者一乘就是 `n log n`。很多人只看到递归深度就说 `O(log n)`，那是漏算了每层的合并。空间上常见数组写法要 `O(n)` 的辅助数组，这也是它和快排比最常被拿出来说的代价。

> 归并排序的时间复杂度的分析，同样是基于分治法。

- **有人看到递归只有 `log n` 层，就说归并排序是 `O(log n)`，你怎么顶回去？**

  `log n` 只是层数，每层还要合并。拿 `n = 8` 画一下：`3` 层，每层合并都要搬 `8` 个元素，总共 `24` 次左右，正好是 `8 × 3`，不是 `3`。

- **`mergeArr` 里两个指针，怎么一眼看出它是线性的？**

  `i` 和 `j` 只往前走不回头，每走一步就往 `res` 里放一个元素，所以总步数就是两个数组长度之和。最后的 `concat(arr1.slice(i))` 也只是把剩下的搬过去，还是线性。

- **输入已经有序了，归并能不能比 `O(n log n)` 快？**

---

> 以上是免费部分。完整内容需要「前端进阶之旅」会员，原文：https://feinterview.poetries.top/docs/algorithm/algorithm-interview/20-%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98%EF%BC%88%E4%B8%8B%EF%BC%89
