归并排序为什么是典型分治算法？稳定性和复杂度怎么分析？

简化版

归并排序是典型的分治算法：把数组分成左右两半，分别排好序，再把两个有序数组合并。

它的时间复杂度稳定是 O(n log n)，额外空间通常是 O(n)。

如果合并时相等元素优先取左边，归并排序就是稳定排序。

详细版

归并排序分为 3 步：分解、解决、合并。

分解阶段把数组不断二分，直到子数组长度为 1。长度为 1 的数组天然有序。合并阶段用两个指针把左右有序数组合并成一个更大的有序数组。

递归树高度是 log n，每一层合并总成本是 O(n)，所以总复杂度是 O(n log n)。

归并排序的性能稳定，不依赖输入是否接近有序；缺点是需要额外数组保存合并结果。

完整版教学

一、为什么归并排序符合分治思想

分治算法的核心是把一个大问题拆成结构相同的小问题，分别解决后再合并结果。归并排序刚好符合这个模式：排序整个数组，可以拆成排序左半部分和排序右半部分；左右都排好后，再把两个有序序列合并。这里的关键是“合并有序序列”比“合并无序序列”简单得多。

记忆钩子：归并排序的灵魂不是“拆”，而是“两个有序段可以线性合并”。

二、递归拆分过程怎么发生

以 [5,2,4,1] 为例，先拆成 [5,2] 和 [4,1]，再拆成单个元素。单个元素天然有序，然后开始往回合并。

[5,2,4,1]
├─ [5,2]
│  ├─ [5]
│  └─ [2]
└─ [4,1]
   ├─ [4]
   └─ [1]

拆到最小问题后，递归开始回溯，逐层形成有序数组。

三、合并两个有序数组为什么是线性的

合并时用两个指针分别指向左右数组开头。每次比较两个指针指向的元素，把更小的放入临时数组。被放入的元素不可能再参与后续比较，因此每个元素最多移动一次。

左指针	右指针	放入结果	指针移动
较小	较大	左元素	左指针右移
较大	较小	右元素	右指针右移
相等	相等	左元素	保持稳定性

所以一次合并长度为 m+n 的两个有序数组，成本是 O(m+n)。

四、代码模板

实现如下：

function mergeSort(nums) {
  if (nums.length <= 1) return nums
  const mid = Math.floor(nums.length / 2)
  const left = mergeSort(nums.slice(0, mid))
  const right = mergeSort(nums.slice(mid))
  return merge(left, right)
}

function merge(left, right) {
  const ans = []
  let i = 0
  let j = 0
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) ans.push(left[i++])
    else ans.push(right[j++])
  }
  return ans.concat(left.slice(i), right.slice(j))
}

工程实现中常用一个辅助数组反复复用，避免频繁 slice 带来的额外开销。

五、复杂度为什么是 O(n log n)

递归树高度是 log n，因为每次数组长度减半。每一层虽然有很多子问题，但所有子问题合并的元素总数仍然是 n。因此总工作量是：

每层 O(n) × 层数 O(log n) = O(n log n)

空间方面，合并需要辅助数组，通常是 O(n)；递归调用栈是 O(log n)。

六、常见误区与追问

误区：认为归并排序原地 O(1) 空间。 常规归并需要辅助数组，真正原地稳定归并很复杂。
误区：相等时随便取右边。 如果相等时优先取右边，会打乱原相对顺序，稳定性被破坏。
误区：只会写递归，不会解释复杂度。 面试通常会追问递归树每层成本。
追问：归并排序和快排怎么选？ 归并稳定且最坏 O(n log n)，快排平均快但最坏可能退化。
追问：链表排序为什么常用归并？ 链表合并不需要随机访问，拆分用快慢指针，归并非常合适。

这些问题都围绕分治的“拆分成本”和“合并成本”。

七、加强记忆

归并排序记成“拆到单个，回程合并”。拆分让问题规模减半，合并利用左右已有序这个条件线性完成。复杂度用递归树记：高度 log n，每层合并总量 n，所以是 O(n log n)。稳定性记住相等时优先取左边。

简化版

详细版