CSCI3160 L02 · Part 1/4 归并排序

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L02，第 1 部分 / 共 4 部分 · 原件 L02-Divide-and-Conquer-未核.pdf（本地课件） p.1–6 定位：用归并排序建立分治递推，再比较不同分支数与缩减比例。前后：下一份 Part 2

本讲按原件提纲分为：

p.1 标题页。p.2 列出 Sorting、Counting inversions、Dominance counting、Matrix multiplication，以下依此顺序。

分治到底在分什么（p.3）【延伸 L01 p.4】

p.3 When conquering, we tackle the core problem “hidden within” the original problem.

递归已由 #L01-01 定义。本讲新增的难点是：把输入分开后，哪些关系由子问题负责，哪些关系横跨两半，必须留给当前层？归并排序要合并两条有序序列；逆序对要数跨半区的数对。只写“分两半递归”而没有合并工作，通常还没构成完整算法。

Sorting

p.4 分节页。

归并排序与每层成本（p.5–6）【新】

题面（L02-Divide-and-Conquer-未核.pdf · Sorting · p.5）

p.5 Problem: Given an array A of n distinct integers, produce another array where the same integers have been arranged in ascending order.

p.5 按原数组位置分成前后两半：前 $\lceil n/2\rceil$ 项组成 A1，余下 $\lfloor n/2\rfloor$ 项组成 A2；奇数规模两边相差一项，再递归排序。合并时只比较两半尚未输出的第一个元素，输出较小者并推进其指针。为什么不必看后面的元素？每半已经有序，后面不可能比其首个剩余元素更小。

补充／算一遍（数字是我为演示取的，讲义没给）：合并 [2,7] 与 [3,5]：2 与 3 比，输出 2；7 与 3 比，输出 3；7 与 5 比，输出 5；右半空，追加 7。结果 [2,3,5,7]，每个元素只输出一次，线性合并。

补充：合并循环的不变量。 已输出的前缀始终有序，且恰好包含两半中已经取走的那些最小元素。初始前缀为空，性质成立。两半各自有序，剩余所有元素的最小者必在两边当前头部之一；取两者较小值，不会把更小的未输出元素留在后面，性质因而继续成立。某半为空后，另一半已有序，直接追加即可。结束时每个输入元素恰被取走一次，才同时得到“有序”和“不丢不重”两个正确性条件。

原演示的状态如下；i,j 是已经从左右各取走多少个元素：

i,j	已输出	下一步
0,0	空	取左边 2
1,0	2	取右边 3
1,1	2,3	取右边 5
1,2	2,3,5	右半耗尽，追加 7

一次循环至少消耗一个元素，因此总迭代不超过两半长度之和；不能因为循环内有左右两支，就把成本再乘一次 n。通常实现使用一块长度 n 的辅助数组；递归调用总数多，并不要求为所有历史调用永久保留各自的副本。

自测：若输入允许重复，合并时相等取哪侧？

单为数值有序，任选一侧均可。若还要求稳定排序，即原来同值元素的先后次序不变，应先取左侧，因为左侧来自更早的原位置。稳定性是附加规格，讲义的互异输入没有这个歧义。

p.6 $f(n)\le 2\cdot f(\lceil n/2\rceil)+O(n)$

公式按讲义重排。p.6 的两个递归调用都要计费。忽略取整来看，第 $j$ 层有 $2^j$ 个规模 $n/2^j$ 的问题，所以合并总量为 $2^j\cdot n/2^j=n$ ；约 $\log_2 n$ 层，得到 $O(n\log n)$ 。演示 $n=8$ 时，三层合并工作量分别是 8、8、8，而不是只计算根节点的 8。

补充对应的往年题演练见附录 A4。

由 p.5 展开的完整递归（空数组和单元素直接返回）：

MergeSort(A):
  若 size(A) <= 1：返回 A
  m = ceil(size(A)/2)
  L = MergeSort(A 的前 m 项)
  R = MergeSort(A 的其余项)
  i = 0；j = 0；out = 空数组
  当 i < size(L) 且 j < size(R)：
    若 L[i] < R[j]：把 L[i] 追加到 out；i 加 1
    否则：把 R[j] 追加到 out；j 加 1
  依次追加 L 尚未用完的后缀，再追加 R 尚未用完的后缀
  返回 out

每轮使 i 或 j 增加 1，合并最终写出恰好 n 个元素，因此每层每个子问题的合并费用与其规模成正比。递归以单元素有序为基础；若两子问题返回有序且不丢元素，合并的不变量保证父问题也有序且元素恰好相同。这同时证明了终止、输出内容和排序性。

本讲核心考点

递归树每层成本与层数共同决定总时间（p.5–6；A 级：Midterm-2021T1 Q2(b)、Final-2021T1 Part II Q1）。

附录

A4 作业/往年题演练（非讲义内容）：递推树的三个往年变化

题面（Midterm-2021T1-题目.pdf · Q2(b) · p.1）

p.1 “(b) Consider a divide-and-conquer algorithm A to solve a problem: divide an instance I of size n into k subinstances of size n/t in time O(n), and then combine solutions of subinstances in time O(n) to obtain a solution for I. Determine value of (k, t) to make A run as fast as possible.”

“(1) (3, 2) (2) (4, 2) (3) (8, 4) (4) (9, 3) (5) (12, 6).”

递推为 T(n)≤kT(n/t)+cn。第 j 层 kʲ 个问题，每个规模 n/tʲ，合计 cn(k/t)ʲ；五组都有 k>t，所以越往下总工作越大，深度约 log_t n，末层主导到 n 的 log_t k 次方。五个指数依次约为 1.585、2、1.5、2、1.387，最小的是 (12,6)。子问题个数12最多仍最快，因为每个子问题缩得更小；不能只比较 k。

题面（Review-Quiz-2020T2-题目.pdf · Q4 · p.1；公式按原题重排）

p.1 “4. Consider the following proposal to improve the $\Theta(n^{\log_2 3})$ -time algorithm for multiplying two n-digit integers x and y: Split x (respectively y) into four roughly $\frac n4$ -digit integers, and recursively compute multiplications of $\frac n4$ -digit integers. Suppose that we can compute product xy by k multiplications of $\frac n4$ -digit integers plus O(n)-time for addition. Determine the largest value k that can make an improvement in running time.”

本题已经假设存在这样的乘法分解，不要求发明具体恒等式。要严格快于旧算法，需 log_4 k<log_2 3；把右边乘2得到 log_2 k<log_2 9，故 k<9，最大整数为8。k=8 时为 n^1.5；k=9 则指数等于原算法，只是相同阶，不能称渐近改进。这里的整数乘法是历史题的应用情境，当前 L02 教的是矩阵乘法，不把旧题算法当成新课件漏讲的章节。

题面（Final-2021T1-题解.pdf · Part II Q1 · PDF p.3 右栏，印刷 p.6；扫描件，视觉读取）

p.3 “1. Determine the asymptotically tight solution for $T(n)=9T(n/3)+\Theta(n^2)$ .”

公式按原题重排。第 j 层共有9ʲ项，每项非递归成本与 (n/3ʲ)² 同阶，相乘恰是 n²。共有 Θ(log n) 层，因此总成本 Θ(n²log n)。叶层的 Θ(n²) 小于各内部层总和。这道题要求紧界，单写 O(n²log n) 只给上界，不完整。

回到正文：本讲正文

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L02-Divide-and-Conquer-未核.pdf（本地课件），本部分 p.1–6；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。