应用：逆序对、外排序与 Timsort

基于通用算法套路 · 核于 2026-07

速查

• 逆序对计数：在 merge 过程中「右段元素先被取走」时，说明左段剩余元素都比它大，此时累加 mid - i + 1 对逆序对——把 O(n²) 暴力优化到 O(n log n)，是归并排序的高频考点。
• 外排序：数据量大到内存放不下时，把数据分块（每块内存能放下）逐块排序后落盘，再用**多路归并（k-way merge）**把所有有序块合并——归并的顺序访问特性让它对磁盘/磁带极友好。
• 多路归并（k-way）：k 个有序块归并，用最小堆每次取 k 路的最小值，总时间 O(n log k)；这是「合并 k 个有序链表」「海量数据外排序」的统一解法。
• Tape 排序（磁带排序）：外排序的经典模型——数据在磁带上只能顺序读/写，用多路平衡归并（如 2 路/4 路）在多条磁带间反复归并。
• Timsort：Python sorted/list.sort 与 Java 对象排序的算法——在归并框架上融合插入排序：识别已有序的「run」、对短 run 用插入排序、再归并；利用现实数据「部分有序」的特性，最好情况接近 O(n)。
• 链表归并排序：链表场景下归并排序是最优解——用「快慢指针找中点」对半切，改指针而非搬数组，做到 O(1) 额外空间（无需临时数组），稳定且 O(n log n)。
• 为何数据库/文件排序爱用归并：①稳定（多关键字排序必需）；②顺序 I/O（对磁盘友好，随机 I/O 昂贵）；③可外排序（数据量超内存）；④可多路并行——这几条让归并成为外部排序的事实标准。
• 逆序对的「左段剩余」公式：merge 中 a[j] < a[i]（取右段）时，左段 [i, mid] 全部大于 a[j]，逆序对数 += mid - i + 1。
• 小数据切插入：Timsort/工业归并普遍在段长 ≤ 16~64 时切回插入排序，因为小数组插入排序常数更小。
• 交互演示：归并排序可视化。

一、逆序对计数：merge 的副产品

逆序对：数组中满足 i < j 且 a[i] > a[j] 的元素对数，是衡量数组「乱序程度」的指标（完全有序为 0，完全逆序为 n(n-1)/2）。暴力双循环是 O(n²)，但在归并排序的 merge 阶段可顺便统计，降到 O(n log n)。

核心洞察：merge 时如果右段元素 a[j] 被取走（即 a[j] < a[i]），说明左段从 i 到 mid 的所有元素都比 a[j] 大（因为左段有序且 a[i] 是左段剩余最小），它们与 a[j] 都构成逆序对——一次性累加 mid - i + 1。

let count = 0;                          // 全局逆序对计数

function mergeAndCount(a, l, mid, r, tmp) {
  for (let k = l; k <= r; k++) tmp[k] = a[k];
  let i = l, j = mid + 1, k = l;
  while (i <= mid && j <= r) {
    if (tmp[i] <= tmp[j]) {             // 左段小，正常取
      a[k++] = tmp[i++];
    } else {                            // 右段小：左段剩余都 > tmp[j]
      count += mid - i + 1;             // ★ 逆序对 += 左段剩余个数
      a[k++] = tmp[j++];
    }
  }
  while (i <= mid) a[k++] = tmp[i++];
  while (j <= r)   a[k++] = tmp[j++];
}

function sort(a, l, r, tmp) {
  if (l >= r) return;
  const mid = (l + r) >> 1;
  sort(a, l, mid, tmp);
  sort(a, mid + 1, r, tmp);
  mergeAndCount(a, l, mid, r, tmp);     // 合并时统计逆序对
}

为什么对？归并排序的每层 merge 只统计跨越左右两段的逆序对，而段内逆序对在更深的递归层已经被统计过了——分治保证了每对逆序对恰好被统计一次（在它俩首次分属左右两段的那个 merge 层）。总复杂度 O(n log n)。

考点：逆序对也可用树状数组/线段树（离散化后单点更新 + 前缀查询，O(n log n)），但归并解法无需离散化、常数小，是面试最常考的解法。LeetCode 剑指 Offer 51「数组中的逆序对」即此题。

二、外排序：海量数据分块 + 多路归并

当数据量远超内存（如 100GB 日志排序）时，数据无法整体载入，必须用外排序（External Sort）——它正是为归并思想量身定做的场景。

两阶段算法

1. 分块排序：把数据切成若干个「内存能装下」的块（如每块 1GB），逐块读入内存、用内排序（如快排）排好、写回磁盘。结果是磁盘上躺着一堆有序块（run）。
2. 多路归并：用 k 路归并把这些有序块合并成一个大的有序文件——同时打开 k 个块的读指针，每次取 k 路的最小值写入输出，用到一个小堆维护。

k 路归并（用最小堆）

function mergeKSorted(arrays) {          // arrays: k 个有序数组
  const h = new MinHeap((x, y) => x.val - y.val);
  for (let i = 0; i < arrays.length; i++) // 初始各路首元素入堆
    if (arrays[i].length) h.push({ val: arrays[i][0], k: i, idx: 0 });
  const res = [];
  while (h.size()) {
    const { val, k, idx } = h.pop();
    res.push(val);
    if (idx + 1 < arrays[k].length)       // 该路还有下一个，继续入堆
      h.push({ val: arrays[k][idx + 1], k, idx: idx + 1 });
  }
  return res;
}

时间复杂度 O(n log k)（n 个元素，每次入/出堆 O(log k)）。这是「合并 k 个有序链表」（LeetCode 23）和「外排序归并阶段」的统一模型。

为什么归并适合外排序

• 顺序 I/O：归并的两路各自从头扫到尾，是纯顺序访问，对磁盘（顺序快、随机慢）和磁带（只能顺序）极友好；而快排的随机访问模式在磁盘上会疯狂寻道。
• 内存可控：k 路归并只需每路保留一个缓冲区（如几 MB），内存占用 O(k·缓冲) 远小于总数据量。
• I/O 次数少：每个元素在归并阶段只被读写常数次（每轮归并一次），可配合「增大 k 减少归并轮数」进一步降 I/O。

Tape 排序（磁带排序）

外排序的经典抽象——数据在磁带上，只能顺序读写、不能随机跳转。典型方案是多路平衡归并：用 2k 条磁带（k 路归并），把初始有序块轮流分到 k 条磁带，每轮从这 k 条读、归并写到另外 k 条，反复直到合成一条有序带。这是 1950 年代外排序的标准方法，至今原理未变。

三、Timsort：归并 + 插入的现实王者

Timsort 是 Tim Peters 于 2002 年为 Python 设计的混合排序算法，现已被 Python、Java（对象排序）、Android、V8（部分）采用。它的核心是「在归并框架上融合插入排序，并利用现实数据的部分有序性」：

1. 识别 run：扫描数组，把已经有序（升序或严格降序，降序则原地反转）的连续段称为一个 run——现实数据往往部分有序，run 可以很长。
2. 短 run 用插入排序扩长：run 长度低于阈值（通常 32~64）时，用插入排序把后续元素补进来扩展到阈值长度——插入排序在小数组上常数极小。
3. run 入栈 + 合并：把 run 压入栈，当栈顶几个 run 的长度关系违反「保持近似平衡」的不变式时，用归并把它们合并——合并时还用「galloping mode」（连续一端取多时批量取）加速。
4. 稳定：全程保证稳定性（合并规则与归并排序一致）。

复杂度：最好 O(n)（完全有序，全是长 run 几乎不合并）；平均/最坏 O(n log n)；空间 O(n)。它本质是「自适应的归并排序」——数据越有序越快，这正是它取代纯归并/纯快排成为主流库默认的原因。

算法	平均	最好	最坏	空间	稳定	特点
归并	O(n log n)	O(n log n)	O(n log n)	O(n)	是	三态一致
Timsort	O(n log n)	O(n)	O(n log n)	O(n)	是	自适应，部分有序快

四、链表归并排序：O(1) 额外空间

在数组上归并必须 O(n) 辅助空间（搬元素），但在链表上，归并通过改指针而非搬数据，可做到 O(1) 额外空间——这让归并成为链表排序的最优解（快排不适合链表，因为链表不能高效随机取 pivot）。

function sortList(head) {
  if (!head || !head.next) return head;          // 递归基
  // 快慢指针找中点，断成两段
  let slow = head, fast = head.next;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  const right = slow.next; slow.next = null;     // ★ 断开成两半
  // 递归排序两半再合并
  return mergeList(sortList(head), sortList(right));
}

function mergeList(a, b) {                       // 合并两个有序链表（改指针）
  const dummy = { next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }  // 稳定：相等取 a
    else              { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;                            // 收尾
  return dummy.next;
}

要点：用快慢指针找链表中点对半切（快指针走 2 步、慢指针走 1 步，快到尾时慢在中点），无需随机访问；merge 时只改 next 指针，不分配新节点，额外空间 O(1)（递归栈 O(log n)，迭代版可消除）。时间 O(n log n)，稳定。LeetCode 148「排序链表」即此题。

五、为何数据库 / 文件排序爱用归并

把以上几点汇总，就理解了为什么数据库的 ORDER BY、文件排序（如 sort 命令、Hadoop 的 shuffle+sort）几乎都基于归并：

1. 稳定：SQL 多列排序（ORDER BY a, b）要求后一列不能打乱前一列的次序，必须稳定——归并是稳定的，快排/堆排不是。
2. 顺序 I/O 友好：数据库排序往往数据量超内存（要落临时文件/磁盘），归并的顺序访问让磁盘 I/O 高效；随机访问的快排会严重拖慢。
3. 可外排序：归并天然支持「分块内排序 + 多路归并」，能处理任意大数据量。
4. 可多路并行：多路归并的各路独立，易于并行化（分布式排序如 MapReduce 的 sort 阶段本质就是分布式归并）。

实际上，数据库引擎（如 MySQL、PostgreSQL）的排序模块通常是「内存够用时用快排/内省排序，内存不够时切到归并（外排序）」的自适应混合——但归并始终是外排序阶段的唯一选择。

交互演示

• 归并排序可视化演示 —— 逆序对计数与 merge 关系的直观对照

下一步

掌握了归并的应用后，下一步把所有要点收口成一张速查表——复杂度、两种代码模板、merge/逆序对模板、与各排序对比、易错点，见参考。