归并排序

场景引入

归并排序是第一个打破 O(n²) 屏障的排序算法，也是分治思想最经典的应用之一。它的核心理念简洁而有力：把一个大问题拆成两个小问题，分别解决后再合并结果。

在实际工程中，归并排序有不可替代的价值：

• 稳定的 O(n log n)：不像快速排序那样有最坏退化的风险
• 天然适合链表排序：不需要随机访问，额外空间可降到 O(1)
• 外部排序的基础：当数据量超出内存时，归并排序是唯一可行的方案

核心思路

归并排序遵循经典的分治三步：

1. 分（Divide）：将数组从中间一分为二
2. 治（Conquer）：递归地对左半和右半分别排序
3. 合（Merge）：将两个有序数组合并为一个有序数组

merge 函数详解

归并排序的核心在于 merge 函数——将两个已排序的数组合并为一个有序数组：

1. 准备两个指针 i 和 j，分别指向左右数组的头部
2. 比较 left[i] 和 right[j]，将较小的放入结果数组
3. 移动对应指针
4. 当一个数组遍历完后，将另一个数组的剩余元素全部放入结果

这个过程是 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, 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;
}

原地归并（减少空间开销）

LeetCode 中通常使用原地归并以减少 slice 的开销：

function mergeSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;

  const mid = (left + right) >> 1;
  mergeSortInPlace(arr, left, mid);
  mergeSortInPlace(arr, mid + 1, right);

  // 原地合并 [left, mid] 和 [mid+1, right]
  const temp = [];
  let i = left, j = mid + 1;
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) temp.push(arr[i++]);
    else temp.push(arr[j++]);
  }
  while (i <= mid) temp.push(arr[i++]);
  while (j <= right) temp.push(arr[j++]);

  for (let k = 0; k < temp.length; k++) {
    arr[left + k] = temp[k];
  }
}

应用：归并排序求逆序对

归并排序的 merge 过程天然适合计算逆序对数量。当 left[i] > right[j] 时，left[i..mid] 中的所有元素都与 right[j] 构成逆序对。

function countInversions(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return 0;

  const mid = (left + right) >> 1;
  let count = 0;
  count += countInversions(arr, left, mid);
  count += countInversions(arr, mid + 1, right);

  const temp = [];
  let i = left, j = mid + 1;
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
      temp.push(arr[i++]);
    } else {
      count += mid - i + 1; // 关键：left[i..mid] 都大于 right[j]
      temp.push(arr[j++]);
    }
  }
  while (i <= mid) temp.push(arr[i++]);
  while (j <= right) temp.push(arr[j++]);

  for (let k = 0; k < temp.length; k++) arr[left + k] = temp[k];
  return count;
}

复杂度分析

	时间复杂度	空间复杂度
最好	O(n log n)	O(n)
平均	O(n log n)	O(n)
最坏	O(n log n)	O(n)

稳定性：稳定。merge 时 left[i] <= right[j] 使用 <=，保证相等元素保持原有相对顺序。

递归深度：O(log n)，因为每次将数组对半分。

为什么需要 O(n) 额外空间？ 合并两个有序数组时，需要临时数组存放结果。这是归并排序相比快速排序的劣势。

面试要点

• 归并排序是稳定的 O(n log n) 排序算法，这在面试中非常重要
• 掌握 merge 函数是关键——很多题目本质上都是"合并两个有序序列"
• 理解分治递归的时间复杂度推导：T(n) = 2T(n/2) + O(n) = O(n log n)
• 求逆序对是高频面试题，必须掌握归并排序的解法

LeetCode 练习

• LC 912. 排序数组 — 归并排序标准实现
• LC 148. 排序链表 — 链表归并排序，空间可优化到 O(1)
• LC 剑指 Offer 51. 数组中的逆序对 — 归并排序经典应用
• LC 315. 计算右侧小于当前元素的个数 — 归并排序进阶应用
• LC 23. 合并 K 个升序链表 — merge 思想的扩展