归并排序

核心思路（Divide & Conquer）

• 分：把区间 [l, r] 二分到只剩 1 个元素（天然有序）。
• 治：将两个有序子数组合并成更大的有序数组（merge）。
• 关键：合并阶段保持“两指针线性扫描”，总比较/移动次数为 O(n)。

[l, r]
 ├─ [l, mid]
 │   ├─ ...
 │   └─ merge
 └─ [mid+1, r]
     ├─ ...
     └─ merge
→ 向上逐层归并

代码实现

mergeSortStable.js

export default function mergeSort(arr) {
  const l = 0
  const r = arr.length - 1

  function _merge(arr, l, r) {
    if (l >= r) return
    const mid = (l + r) >> 1

    _merge(arr, l, mid)
    _merge(arr, mid + 1, r)

    let i = l, j = mid + 1
    const tmp = []

    while (i <= mid && j <= r) {
      if (arr[i] < arr[j]) tmp.push(arr[i++])
      else tmp.push(arr[j++])
    }
    while (i <= mid) tmp.push(arr[i++])
    while (j <= r)  tmp.push(arr[j++])

    for (let k = l, t = 0; k <= r; k++, t++) arr[k] = tmp[t]
  }

  _merge(arr, l, r)
}

mergeSortStable.ts

export default function mergeSort(arr: number[]): void {
  const l = 0
  const r = arr.length - 1

  const _merge = (arr: number[], l: number, r: number): void => {
    if (l >= r)
      return
    const mid = (l + r) >> 1

    _merge(arr, l, mid)
    _merge(arr, mid + 1, r)

    let i = l
    let j = mid + 1
    const tmp: number[] = []

    while (i <= mid && j <= r) {
      if (arr[i] < arr[j]) {
        tmp.push(arr[i++])
      }
      else {
        tmp.push(arr[j++])
      }
    }

    while (i <= mid) tmp.push(arr[i++])
    while (j <= r) tmp.push(arr[j++])

    for (let i = l, j = 0; i <= r; i++, j++) {
      arr[i] = tmp[j]
    }
  }

  _merge(arr, l, r)
}

优点：结构清晰；合并过程是标准线性归并，整体时间可达 O(n log n)。

可改进点：

1. 小数组优化：区间很小时（如 <= 16）可改用插入排序，提升常数性能。
2. 递归深度：超大数组在 JS 中可能栈溢出；可用**自底向上（迭代）**版本避免递归。
3. 比较函数：若要支持对象或自定义比较，应允许传入 cmp(a,b)。

复杂度与性质

• 时间复杂度：T(n) = 2T(n/2) + O(n) ⇒ O(n log n)（最好/平均/最坏均如此；“天然有序/自然归并”可达接近 O(n)）。
• 空间复杂度：数组实现通常需要 O(n) 额外空间（临时缓冲）+ 递归栈 O(log n)；合计仍记作 O(n)。
• 稳定性：算法可稳定，但实现细节决定稳定与否（相等元素时先取左侧）。
• 适用场景：外部排序、大数据分块排序，或需要稳定性的场景。

*稳定 + 复用缓冲 + 小区间优化的改进版

export function mergeSortStable(arr, cmp = (a, b) => (a > b) - (a < b)) {
  const n = arr.length
  if (n <= 1) return arr
  const buf = new Array(n)

  // 小区间阈值，可按场景调参（16~32）
  const TH = 16

  function insertion(a, l, r) {
    for (let i = l + 1; i <= r; i++) {
      const x = a[i]
      let j = i - 1
      while (j >= l && cmp(a[j], x) > 0) { a[j + 1] = a[j]; j-- }
      a[j + 1] = x
    }
  }

  function _ms(a, l, r) {
    if (r - l + 1 <= TH) { insertion(a, l, r); return }
    const mid = (l + r) >> 1
    _ms(a, l, mid)
    _ms(a, mid + 1, r)

    // 若已经有序可跳过合并（优化）
    if (cmp(a[mid], a[mid + 1]) <= 0) return

    // 归并到 buf 再拷回 a（稳定：相等时取左）
    let i = l, j = mid + 1, k = l
    while (i <= mid && j <= r) {
      if (cmp(a[i], a[j]) <= 0) buf[k++] = a[i++]
      else buf[k++] = a[j++]
    }
    while (i <= mid) buf[k++] = a[i++]
    while (j <= r)  buf[k++] = a[j++]
    for (let t = l; t <= r; t++) a[t] = buf[t]
  }

  _ms(arr, 0, n - 1)
  return arr
}

要点：

• 稳定性：cmp(a[i], a[j]) <= 0 时优先取左侧；
• 一次性缓冲：buf 只分配一次，减少 GC 压力；
• 小数组优化：插入排序对小规模子问题更快；
• 有序性剪枝：若 a[mid] <= a[mid+1]，说明两段整体已序，省掉一次合并。

自底向上（迭代）版（避免递归栈）

export function mergeSortBottomUp(arr, cmp = (a, b) => (a > b) - (a < b)) {
  const n = arr.length
  if (n <= 1) return arr
  const buf = new Array(n)

  for (let width = 1; width < n; width <<= 1) {
    for (let l = 0; l < n; l += width << 1) {
      const mid = Math.min(l + width - 1, n - 1)
      const r   = Math.min(l + (width << 1) - 1, n - 1)
      if (mid >= r) continue
      if (cmp(arr[mid], arr[mid + 1]) <= 0) continue

      let i = l, j = mid + 1, k = l
      while (i <= mid && j <= r) {
        if (cmp(arr[i], arr[j]) <= 0) buf[k++] = arr[i++]
        else buf[k++] = arr[j++]
      }
      while (i <= mid) buf[k++] = arr[i++]
      while (j <= r)  buf[k++] = arr[j++]
      for (let t = l; t <= r; t++) arr[t] = buf[t]
    }
  }
  return arr
}

适用：非常大数组或需避免递归栈；与自顶向下性能相近，常数因实现而异。

性质

• 归并排序：稳定；O(n log n)；空间 O(n)（数组）；链表可 O(1) 额外空间。
• 快速排序：通常更快、原地 O(log n) 栈，但不稳定，最坏 O(n^2)（可随机化/三数取中缓解）。
• 堆排序：O(n log n)、原地、不稳定，常数大。
• Timsort（Python/Java 等）：利用“自然有序 runs”与“插入排序 + 改进归并（如 galloping）”的工程级优化，稳定且对真实数据更快。

延伸与外部排序

• 自然归并：先识别输入中已有的有序段（runs），可减少归并轮数，接近线性。
• 外部归并排序：数据量大到内存放不下时，分块排序后用多路归并在磁盘上合并。
• 原地归并/块归并：理论可做到 O(1) 额外空间但实现复杂、常数大；工程上少用。

速查总结

• 模板：两指针线性归并；
• 复杂度：O(n log n) 时间，O(n) 额外空间（数组），稳定（取决于实现）。