【算法图解】归并排序：分治思想的典范

如果要选一个最能代表“分治思想”的排序算法，归并排序一定在候选名单里。

它的逻辑非常干净：

• 分：把数组拆到只剩单个元素
• 治：递归排序（单个元素天然有序）
• 合：把两个有序数组合并成一个更大的有序数组

这也是它稳定、复杂度优秀但需要额外空间的原因。

1. 合并（merge）是核心

归并排序的精华不在“拆”，在“合”。

合并两个有序数组时：

• 用两个指针分别指向两边开头
• 每次取更小的那个放进结果

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++])
    } else {
      result.push(right[j++])
    }
  }

  while (i < left.length) result.push(left[i++])
  while (j < right.length) result.push(right[j++])

  return result
}

这段合并逻辑决定了两件事：

• 时间为什么是 $O(n\log n)$
• 为什么它是稳定排序

2. 递归实现（可运行）

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)
}

console.log(mergeSort([5, 2, 4, 6, 1, 3]))

3. 复杂度分析

时间：O(nlogn)

每一层合并的总工作量是 $O(n)$：

• 第一层：合并若干个长度为 1 的数组，总共处理 n 个元素
• 第二层：合并若干个长度为 2 的数组，总共处理 n 个元素
• ...

层数是 $\log n$，所以总时间是 $O(n\log n)$。

空间：O(n)

因为合并时要创建新的数组 result，总体峰值额外空间通常是 $O(n)$。

4. 稳定性：为什么归并是稳定排序？

看合并逻辑里的关键：

• 当 left[i] === right[j] 时，我们先取 left[i]

这保证了：

• 原来在左边的相等元素，排序后仍然在右边相等元素前面

所以归并排序是稳定的。

5. 工程里怎么用？

• 需要稳定性：归并很合适
• 大数据排序：外部排序（External Sort）常用归并思想
• 链表排序：链表做归并很自然，且可以做到 $O(1)$ 额外空间（通过指针拼接）

6. 面试回答模板

• 归并排序是分治：拆分到单元素，再合并两个有序序列。
• 时间复杂度稳定 $O(n\log n)$，最坏也一样。
• 空间复杂度 $O(n)$，因为合并需要辅助数组。
• 它是稳定排序。

总结

• 归并排序是分治的典范，复杂度优秀且稳定。
• 代价是需要 $O(n)$ 额外空间。
• 合并逻辑是你必须掌握的核心。