2.2 Mergesort：归并契约、两种调度与比较下界

2.2 · Mergesort覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“2.2 · Mergesort”如何从稳定归并合同推导自顶向下和自底向上的调度、比较界与辅助空间
  • 能逐项核对 归并排序、抽象原地归并、自顶向下归并排序、自底向上归并排序、归并排序改进，并区分作者站内容与本页独立补充
  • 能按“T(N) = 2T(N/2) + Θ(N) = Θ(N log N)”手算一个最小输入，逐步检查“归并前左右半区分别有序；归并后区间有序、稳定且元素多重集不变”
  • 能注入“未先复制辅助数组就覆盖尚未读取的左半区，或相等键时优先取右侧破坏稳定性”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“2·2 · Mergesort”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“2·2 · Mergesort”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“2·2 · Mergesort”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：2.2 · Mergesort

  • 1. 归并排序：在本页通过“划分有序子段”连接解释、交互状态和练习验收。
  • 2. 抽象原地归并：在本页通过“复制到辅助区”连接解释、交互状态和练习验收。
  • 3. 自顶向下归并排序：在本页通过“比较两侧首项”连接解释、交互状态和练习验收。
  • 4. 自底向上归并排序：在本页通过“写回目标区间”连接解释、交互状态和练习验收。
  • 5. 归并排序改进：在本页通过“核对稳定全序”连接解释、交互状态和练习验收。

从“两个有序队列怎样合成一个”开始

归并排序（mergesort）建立在一个比“排序整个数组”更小的操作上：如果左右两段已经各自有序，只需比较两段当前最小项，就能线性地产生联合有序结果。排序问题因此被拆成divide、sort halves、merge三步。

先预测名称“abstract in-place merge”是否代表Theta(1)额外空间。不是。官方方法把结果写回 a[lo..hi]，但先把整个区间复制到 aux；它在抽象接口上原地留下结果，在现代space分类中仍使用Theta(N)辅助数组。真正常数空间且稳定、线性的通用array merge非常复杂，不是本节实现。

官方2.2依次覆盖 Abstract in-place merge、Top-down mergesort、Improvements、Visualization、Bottom-up mergesort，最后用comparison decision tree说明N log N的渐近最优性。核心问题始终是：两个输入runs是否有序、每次从哪边取、结果写到哪里。

2.2.1 Abstract in-place merge：两个指针的线性契约

抽象原地归并（abstract in-place merge）要求两个closed subarrays各自sorted。先复制 a[lo..hi] 到 aux，令i指向左run开头、j指向右run开头，再从k等于lo开始写回。

private static void merge(
        Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    assert isSorted(a, lo, mid);
    assert isSorted(a, mid + 1, hi);
 
    for (int k = lo; k <= hi; k++)
        aux[k] = a[k];
 
    int i = lo;
    int j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)                   a[k] = aux[j++];
        else if (j > hi)                    a[k] = aux[i++];
        else if (less(aux[j], aux[i]))      a[k] = aux[j++];
        else                                a[k] = aux[i++];
    }
    assert isSorted(a, lo, hi);
}

Merge loop不变量是：写入 a[lo..k) 的恰是两段已消费元素，并且它们是原联合区间最小的 k-lo 项，顺序非降；aux[i..mid] 与 aux[j..hi] 仍各自有序。两端都未耗尽时，next minimum必在两个heads之一；取较小head后不变量前进一项。

稳定归并（stable merge）依赖最后一个else。Code只在right严格小于left时取right，相等时取left；若改成“小于等于时取right”，输出仍sorted，却会让右half中的equal record跨过左half record。

2.2.2 Top-down mergesort：递归树从叶子向上合并

自顶向下归并排序（top-down mergesort）先为整次sort分配一次N-length aux，避免每个recursive call重复allocation。Base case hi <= lo 覆盖empty或single item，它们天然sorted。

private static void sort(
        Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}
 
public static void sort(Comparable[] a) {
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length - 1);
}

正确性用structural induction证明。Base interval长度至多1，命题成立；归纳步假设两个recursive calls分别排好左右half，满足merge precondition，merge后整个interval sorted且permutation保持。Termination来自每次interval严格缩短，mid使用 lo + (hi-lo)/2 也避免indices求和overflow。

对N为2的幂，比较成本满足：

C(N)=2C(N/2)+M(N),N/2≤M(N)≤N−1C(N)=2C(N/2)+M(N), \qquad N/2\le M(N)\le N-1

Recursion tree有lg N个merge levels，每层所有runs总长度为N，因此官方命题给出约 1/2 N lg N 到 N lg N 次比较，并至多 6N lg N 次array accesses。不是2的幂时最后层不完整，但渐近界与线性每层逻辑不变。

每次merge把区间从a复制到aux，约2N accesses，再从aux读取并写回a，比较与exhaustion paths带来额外reads；6N lg N是便于验证的上界，不是每个输入的精确计数。Auxiliary array保存N个references，递归栈深度为Theta(log N)，总extra space仍由Theta(N)主导。

2.2.3 稳定性、输入无关保证与边界

Top-down mergesort无论输入升序、逆序还是随机，都建立同一recursion shape；未经改进时每个internal node都会merge。因此worst-case和best-case都在Theta(N log N)量级，而selection/insertion的输入敏感模式不同。Guarantee适合需要可预测延迟的场景，但N-length aux可能成为memory或allocation约束。

全算法稳定性由两层组成：recursive children已stable，merge对equal heads先取左。只在leaf稳定不够，只在final merge稳定也不够；每个level都必须保留原相对顺序。Index sort则可对indices做stable merge，返回permutation而不重排原objects，适合large records或只需order view的场景。

2.2.4 Mergesort improvements：削减常数但保留证明

归并排序改进（mergesort improvements）在不改变worst-case N log N保证的前提下降低常数。官方 MergeX 同时使用三项：

  1. 对长度不超过cutoff的subarray使用insertion sort，减少tiny recursive calls；current official cutoff为7。
  2. 两half排好后检查 src[mid] <= src[mid+1]，若边界已序就整段copy或跳过merge。
  3. Recursive calls交换src与dst角色，让一个level从a读向aux写，下一个level反向，省去每次merge前的显式copy。
private static void sort(
        Comparable[] src, Comparable[] dst, int lo, int hi) {
    if (hi <= lo + CUTOFF) {
        insertionSort(dst, lo, hi);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(dst, src, lo, mid);
    sort(dst, src, mid + 1, hi);
 
    if (!less(src[mid + 1], src[mid])) {
        System.arraycopy(src, lo, dst, lo, hi - lo + 1);
        return;
    }
    merge(src, dst, lo, mid, hi);
}

边界检查让已排序input的比较recurrence变成 T(N)=2T(N/2)+1，解为Theta(N)，但recursive calls仍存在。Ping-pong版本消除copy时间，不消除Theta(N)辅助空间；src/dst initial contents、base-case写入目标和return后output owner必须成套设计，否则某层会读到未排序旧数据。

Cutoff不是理论常数，应在目标runtime、item type和comparator上benchmark。太小几乎无收益，太大让quadratic insertion work占主导。优化验收必须保持stable labels、permutation和all boundary lengths，特别是cutoff减1、cutoff、cutoff加1。

2.2.5 Visualization：区分递归顺序与数据顺序

Mergesort visualization通常把数组画成柱条，并在每次merge标出 lo/mid/hi。需要同时展示两种顺序：call tree按left child、right child、parent进行postorder；数据则在每个merge中按两个head的key写回。只画最终柱高会隐藏aux复制、tie choice和短尾run。

Top-down merge size由recursive split决定，常出现2、4、8式向上汇聚；非2的幂会产生不对称sizes。可视trace应在每帧标出source array、destination array、已消费pointer和已证明有序的output prefix，才能用于定位off-by-one，而不是只做动画。

2.2.6 Bottom-up mergesort：按run长度迭代调度

自底向上归并排序（bottom-up mergesort）不显式构建recursion tree。第一个pass合并1-by-1，第二个合并2-by-2，之后4-by-4，直到一个run覆盖全数组。

public static void sort(Comparable[] a) {
    int n = a.length;
    Comparable[] aux = new Comparable[n];
 
    for (int len = 1; len < n; len *= 2) {
        for (int lo = 0; lo < n - len; lo += len + len) {
            int mid = lo + len - 1;
            int hi = Math.min(lo + len + len - 1, n - 1);
            merge(a, aux, lo, mid, hi);
        }
    }
}

Inner guard lo < n-len 保证右run至少有一项；Math.min 处理数组尾部不足2len的短run。每个pass结束后，所有completed output runs长度至多2len且各自sorted；len doubling后把相邻runs再合并。它与top-down使用相同merge、稳定性、比较界和Theta(N)辅助空间，但merge调用顺序不同，且没有recursive stack。

从run length 1开始每轮double，覆盖N项所需pass数为：

P(N)=⌈lg⁡N⌉P(N)=\lceil\lg N\rceil

Bottom-up也适合链表，因为相邻runs可通过pointer重连而不需要随机访问；对于stream/external sorting，还能把已排序runs逐层合并。Array版本仍需aux，不应因为“非递归”就误称constant-space。

2.2.7 Comparison lower bound：为什么N log N是渐近最优

比较排序下界来自decision tree。N个distinct keys有N!种输入orders；每次binary comparison最多把可能性分成两支，因此tree至少有N! leaves，height至少：

H≥⌈lg⁡(N!)⌉H\ge\lceil\lg(N!)\rceil

Stirling approximation给出：

lg⁡(N!)=Nlg⁡N−(lg⁡e)N+O(lg⁡N)∼Nlg⁡N\lg(N!)=N\lg N-(\lg e)N+O(\lg N) \sim N\lg N

Mergesort worst case至多约N lg N compares，与任何comparison-based algorithm的保证下界同阶，所以是asymptotically optimal comparison sort。这个结论不禁止linear integer sorting：counting/radix sorts利用key representation，不只通过pairwise comparisons，属于不同model。也不代表mergesort在常数、空间、cache或特殊input上总是最佳。

Merge还能在线性对数时间计数inversions：merge时若right head小于left head，则它与左run剩余的 mid-i+1 项都构成逆序。Index mergesort则排序indices而不移动records。两者都复用同一merge invariant，说明稳定的线性merge是一种可组合primitive，而不只是排序步骤。

统一验收：把每个merge变成可核查证据

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“2.2 · Mergesort”的两个最小情境间切换，再逐项选择正式概念。预测“T(N) = 2T(N/2) + Θ(N) = Θ(N log N)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

2.2 · Mergesort：对象、操作与不变量

从稳定归并合同推导自顶向下和自底向上的调度、比较界与辅助空间

选择最小情境

切换正式概念

输入合同操作证书algs4-2.2 · 先给前提，再执行，再验收当前概念：1/6
稳定归并
归并 [(2,a),(4,a)] 与 [(2,b),(3,b)]
当前观察
mergesort：相等键先取左侧，原始相对次序 a 在 b 前
T(N) = 2T(N/2) + Θ(N) = Θ(N log N)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 归并排序：在实验 1 中指出对应状态，并写出一个通过条件。
  • 抽象原地归并：在实验 2 中指出对应状态，并写出一个通过条件。
  • 自顶向下归并排序：在实验 3 中指出对应状态，并写出一个通过条件。
  • 自底向上归并排序：在实验 1 中指出对应状态，并写出一个通过条件。
  • 归并排序改进：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“T(N) = 2T(N/2) + Θ(N) = Θ(N log N)”不是孤立结论？

问题 3：故障恢复。 怎样证明“未先复制辅助数组就覆盖尚未读取的左半区，或相等键时优先取右侧破坏稳定性”已经修复？

本章回顾

  1. Mergesort把两个sorted runs的线性merge组合成divide-and-conquer排序。
  2. Abstract in-place merge把结果写回原区间，却仍使用Theta(N) auxiliary array。
  3. Stable merge在equal heads时先取left，output prefix始终是联合输入的最小前缀。
  4. Top-down mergesort递归二分并向上merge，保证Theta(N log N)时间。
  5. Improvements用small cutoff、ordered-boundary test和src/dst换位削减常数，不消除N空间。
  6. Bottom-up mergesort按1、2、4等run sizes迭代，和递归版有相同渐近保证。
  7. Decision tree至少需要lg(N!)级比较，mergesort因此在comparison model中渐近最优。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…