排序算法系列 06：归并排序——分治思想的教科书级应用

从这篇开始，我们进入 O(n log n) 的世界。

前面的冒泡、选择、插入都是 O(n²)——数据量一大就扛不住。归并排序是第一个让你感受到"算法设计可以质变"的排序算法。

它的核心武器是分治：把大问题拆成小问题，解决小问题，再把结果合并起来。

核心思想

把数组对半拆，一直拆到每段只剩一个元素（一个元素天然有序），然后两两合并——合并的时候保持有序。

听起来好像很绕，但其实逻辑特别清晰：

1. 拆到不能再拆
2. 合并的时候排好序

排序的工作实际上发生在"合并"这一步。拆分本身不做任何比较。

走一遍过程

用 [5, 2, 9, 1, 7, 3] 举例。

拆分阶段：

[5, 2, 9, 1, 7, 3]
[5, 2, 9]          [1, 7, 3]
[5] [2, 9]         [1] [7, 3]
[5] [2] [9]        [1] [7] [3]

拆到每段只有一个元素，停。

合并阶段：

[2] + [9]    → [2, 9]
[5] + [2, 9] → [2, 5, 9]

[7] + [3]    → [3, 7]
[1] + [3, 7] → [1, 3, 7]

[2, 5, 9] + [1, 3, 7] → [1, 2, 3, 5, 7, 9]

合并两个有序数组的操作很简单：两个指针分别指向两个数组开头，每次取较小的放入结果。

合并操作详解

这是归并排序最关键的一步。比如合并 [2, 5, 9] 和 [1, 3, 7]：

比较 2 和 1 → 取 1
比较 2 和 3 → 取 2
比较 5 和 3 → 取 3
比较 5 和 7 → 取 5
比较 9 和 7 → 取 7
剩下 9     → 直接放入

结果：[1, 2, 3, 5, 7, 9]

两个有序数组合并成一个有序数组，时间是 O(n)。简单高效。

代码实现

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([5, 2, 9, 1, 7, 3]));
// [1, 2, 3, 5, 7, 9]

代码分两块：

• mergeSort 负责拆——递归地把数组对半切
• merge 负责合——把两个有序数组合成一个

注意 merge 里用的是 <=，这保证了相等元素先取左边的，维持稳定性。

为什么是 O(n log n)？

两个维度：

• 拆分层数：每次对半切，切到单个元素需要 log n 层
• 每层的工作量：每一层所有元素都要参与合并，总共处理 n 个元素

所以总时间 = log n 层 × 每层 O(n) = O(n log n)。

而且这个复杂度是稳定的——不管输入数据是什么样，归并排序都是 O(n log n)。不会像快排那样有最坏情况退化。

复杂度

空间复杂度 O(n)——合并时需要一个同等大小的临时数组。这是归并排序最大的"代价"。

稳定性：稳定。合并时相等元素保持原有顺序。

归并排序的优势场景

1. 需要稳定排序：这是归并排序最大的卖点。快排不稳定，堆排也不稳定，归并稳定且快
2. 链表排序：链表的归并排序可以做到 O(1) 额外空间（因为链表合并不需要额外数组）
3. 外部排序：数据太大内存放不下时，归并排序的"分块处理再合并"思路天然适配磁盘 I/O

和快排的取舍

归并排序和快速排序都是 O(n log n)，但各有侧重：

简单说：要稳定选归并，要速度选快排。实际工程里很多排序实现是两者结合——比如 TimSort 就是归并 + 插入的混合体。

下一篇就来聊快速排序——实际开发中最常见的高性能排序算法。

系列导航

上一篇：排序算法系列 05：希尔排序——给插入排序装个加速器

下一篇：排序算法系列 07：快速排序——面试必问，工程必用