归并排序:把刀挪到正中间MergeSort

教授开场先把两课缝在一起:"The idea is quite similar to insertion sort."(思路和插入排序非常像。)同一个递归骨架,唯一的分歧是——刀往哪里落。

先复盘 InsertionSort 的刀法:在 A[1..n] 的倒数第一格下刀,切出 A[1..n−1] 和孤零零的 A[n]。教授对这一刀的评语:"the first part is really heavy, it contains almost everything."(第一块特别重,几乎装下了一切。)重的那块整个丢给递归,轻的那块自己动手插进去——插一次最多要比 n−1 回,层层叠起来,worst case 结出 Θ(n²)。

输入是讲义全程使用的例子 [8, 1, 9, 2, 8, 4, 6, 5]——注意里面有两个 8,待会儿它俩会在缝合现场狭路相逢,逼我们表态「平局怎么办」。

"We can translate that idea directly into the pseudocode."(想法可以直译成伪代码。)按 3-1 的配方逐行生长:兜底 → 变小 → 递归 → 拼装。

• Base case:n ≤ 1。空数组有序,单元素数组也有序——"nothing to do, we just return the array itself."(啥也不用干,原样返回。)注意是 ≤ 1 而不是 == 0,这个「≤」一个字符扛着整个算法的终止性,§10 坑三见分晓。
• 切点 m = ⌈n/2⌉(上整)。教授的口算示范:n = 5 时 m = 3,两半是 A[1..3](3 个)和 A[4..5](2 个)——"the first half is slightly larger, just one larger."(前半最多只比后半大 1。)n 是偶数时正好对半。
• 两个递归调用 = 借两次黑盒。3-1 的神谕心态原封不动:不追调用栈,信任 BL、BR 各自交回一份排好序的半成品。这份信任待会儿由归纳法背书(§07)。
• 最后一行拼装。两个有序半份进,一个有序整体出——全部新的技术含量都压在这个 Merge 上。

既然全课都在递归主题里,Merge 当然也递归着写。教授还故意把它写得更慷慨:"k and ℓ can be arbitrary numbers... this merge procedure is useful by itself."(两个输入的长度随意,不必相等——这个过程本身就值得单独拥有。)

MergeSort 里喂给它的两半 size 相等或只差 1,但 Merge 不挑食,长短随意——这份慷慨在挑战题 C4 会派上大用场。伪代码:

为什么 base case 有两个?

输入有两个数组,兜底就要把两边都兜住:X 空了就把 Y 整个交出去,Y 空了就交 X——"you're trying to merge two sorted arrays, if one of them is empty, well, you just return the other one. There's nothing to merge."(一边空了,没什么可缝的,另一边本身就是答案。)注意这个 base case 不是摆设:它一口气交付一整段数组,待会儿在合并机里你会看到它「白送」若干元素。

递归情形:最小的工作,换最小的变小

教授把设计问题问到了骨头上:"What's the minimum amount of work we can do to make the input smaller?"(把输入变小,最少要干多少活?)答案:一次比较。比较两个数组的头一个元素 X[1] 和 Y[1]——赢家(较小者)有资格直接站上输出的第一位,理由是一个干净的三段论:

然后是「变小」:贡献了头元素的那个数组去掉头,X[1..k] 缩成 X[2..k],size 减 1;Y 原封不动。教授连安慰都替你想好了:"Smaller by 1 is smaller, and smaller is good."(小 1 也是小,小就够了。)于是递归合法,神谕接管剩下的一切。X[1] > Y[1] 时对称地走 else 支。

教授明明叮嘱过「别开黑盒」,这次却自己没忍住:"it's really tempting to look inside the black box and see how it's happening. I'm fulfilling that request... let's do this anyways, kind of fun."(忍不住想看?我来满足你,反正挺好玩。)这是全课程第二次官方开盒——盒里是两根红箭头。

场景 A 里有一场重头戏:两个 8 狭路相逢。教授的现场裁决:"eight versus eight — it's a draw, let's say that the top one wins, breaking the tie arbitrarily."(平局!就让上面的赢吧——怎么破平局无所谓。)伪代码里这份约定写作 X[1] ≤ Y[1] 的那个「≤」:相等时走 if 支,X 先出列。破法随意,不影响正确性——反正两个 8 谁先谁后,数组照样有序。

同一场缝合还有第三种视角——把递归调用链直接写在纸上(每行就是一层递归,和你刚才按的每一步一一对应):

三个场景的比较次数:7、7、3。上限是 n−1(证明在挑战题 C2 等你),下限能低到 min(k, ℓ)——两边谁先耗尽,决定多少元素是 base case 白送的。

三问的第二问,先问 Merge:多快?但这次有个新情况——输入是两个数组,时间函数的自变量 n 该是什么?

教授的处理干脆利落:X 和 Y "are not really used differently... they're both just input arrays containing numbers"(两个数组没有被区别对待,都只是装数字的容器),所以合并记账——令 n = k + ℓ,总 size。Merge 的时间复杂度函数记作 S(n)。然后照 L1-2 的老规矩逐行数:

• 两行 base case + 一次 X[1] ≤ Y[1] 的比较:常数工作,记 O(1);
• if-else 只走一支 → 恰好一个递归调用,其输入总 size = (k−1) + ℓ 或 k + (ℓ−1) = n − 1(贡献方缩 1,另一方不动);
• 没有别的了。

教授只开了 Merge 一个盒。我们得寸进尺一次:把整趟 MergeSort([8,1,9,2,8,4,6,5]) 全程摊开——先一路切到底,再一路缝回来。(讲义没有这张图,属自费参观;看完记得把盒子还回去。)

似曾相识?3-1 挑战题 C3 的 HalfSum 就是这个形状(对半切、双递归、拼装),当时题解剧透:「这种形状,几周后有个大名鼎鼎的亲戚——MergeSort。」亲戚今天登门了。另外注意:MergeSort 的两个递归调用都会执行(树每层真的裂开),对比 Merge 的 if-else 只执行一个——§08 的式子里会各留一个影子。

讲义 4/4 页在「Correctness?」后面只写了五个词:"Proof by induction. (Exercise)"。教授的原话把台阶都搭好了:"three steps — base case, inductive hypothesis, use that hypothesis to complete your inductive step... I'm sure you can fill in this complete proof."

动笔前清点装备,三件全是旧的:① 归纳三步模板(3-1);② Merge 的正确性定理(§03 已证,归纳步里可以直接引用——教授:"inside your inductive step, obviously you're going to need the correctness of the merge procedure, which we just proved");③ 强归纳的手感(3-1 挑战题 C3:当子问题是对半切出来的,「对 n−1 正确」的弱假设接不住,必须假设「对一切 < n 正确」)。先自己写一遍——这同时就是挑战题 C1——再展开对答案:

第二问轮到 MergeSort 自己:多快?老规矩,设 T(n) 为 MergeSort 处理 size n 输入的时间,照伪代码逐行记账——然后式子停在了一个红色的问号上。

• 第 1 行 base case、第 2 行整数除法:常数,O(1);
• 第 3 行:递归调用,输入 size ⌈n/2⌉ → 按定义记 T(⌈n/2⌉);
• 第 4 行:递归调用,输入 size n − ⌈n/2⌉ = ⌊n/2⌋ → 记 T(⌊n/2⌋);两个调用都会执行(没有 if-else 帮你二选一——§06 的树亲眼看过,每层真的裂开);
• 第 5 行:调用 Merge,总输入 size n → 记 S(n)(§05 的函数,原样嵌进来)。

对比一下历代记账,新东西一目了然:

• RecursiveLinearSearch(3-1):T(n) = T(n−1) + O(1) —— 一个 T;
• InsertionSort(3-2):T(n) = T(n−1) + S(n) —— 一个 T,嵌一个 S;
• MergeSort(本课):T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + S(n) —— 两个 T,还嵌一个没解开的 S。

同一份输入,两位选手,只数一件事:元素之间的比较次数。口径:InsertionSort 记 3-2 递归版 insert 的账(逐格比、不合适就换位),MergeSort 记本课 Merge 的账(每输出一个元素至多比一次)。曲线全部是数出来的,不是公式画的。

MergeSort 的坑,一半在 Merge 的细节里,一半在「以为已经学完了」的错觉里。对号入座。

四道,难度递增。C1 就是讲义亲手发的那张考卷 (Exercise);C3 会把上一课整个装进口袋;C4 用上教授「k、ℓ 任意」的伏笔。先动笔再看解。

无限次尝试,零压力。七道题,把「切—缝—证—记账」这条链各敲一遍。