合併插入排序

Lester Ford, Jr. 以及 Selmer Johnson 把 Howard B. Demuth 的 1957 年博士論文裡面提到的 5 筆資料排序方法進行推廣，最終獲得一個用謹慎的方法試圖減少比較次數的排序方法──合併插入排序 Merge Insertion Sort。 這個排序法的名字是高德納教授（Donald Knuth）在他撰寫的《The Art of Computer Programming》裡面取的。 附帶一提，最近 MIT 教授 Lex Fridman 釋出了一段與 Knuth 的訪談¹：https://www.youtube.com/watch?v=2BdBfsXbST8 大家有興趣可以聽聽看。

如何避免大量的天花板

演算法的核心概念是這樣的：如果看到一個長度為 \(2^k-1\) 元素的序列，那麼此時將一個新的元素插入其中，是最不會浪費「資訊」的。因為資訊理論下界 \(\ceil{\log_2 ((2^k-1)+1)}\) 無論有沒有天花板，其數值都是一樣的，得花費恰巧 \(k\) 次才能夠找出新元素的落點。

如果長度不到 \(2^k-1\) 的序列怎麼辦？盡量讓這件事情不要發生就好了！ 乍看之下很困難啊──但是 Ford-Johnson 盡量做到了，最重要的想法可以透過下面這張圖來傳達：

假設我們能夠經過若干次比較之後，把所有元素的大小關係描述成上面這張圖。其中 \(x\to y\) 代表經過比較以後，我們得出了 \(x < y\) 這項結論。 上圖黃色框線內共有 7 個元素，若我們想將紅色元素插入上面長鏈中，此時恰好達到資訊理論下界的 \(\log_2(7+1) = 3\) 次。因此可以得到結論是：此時優先將紅色元素插入長鏈、再將左邊的藍色元素插入長鏈。其需要的比較次數至多是 \(\log_2(7+1) + \log_2(7+1) = 6\) 次。相反地，若我們先插入藍色元素，再插入紅色元素，在最壞情形下我們得花費 \(\log_2(7+1) + \ceil{\log_2(8+1)} = 7\) 次比較才能達到效果。

行文至此，不難發現，如果我們有辦法把輸入資料的大小關係，表達成上圖這種牙刷形狀，再依照最不浪費比較次數的方式進行二分插入，說不定可以得到較佳（比較次數較小）的排序演算法。

合併插入排序的第一步

要怎麼生出牙刷呢？ 首先，在分而治之的部分，我們先將資料隨意地兩兩分成一組，並且花費 \(\floor{n/2}\) 次比較。 如果有多出來的元素，就先放在旁邊吧。 接下來，我們可以遞迴針對比較大的那些 \(\floor{n/2}\) 元素進行排序，就可以把它們接成一長串了！ 最後是刷毛整理的部分：我們將刷毛由左至右（資料可以命名為 \(b_1, b_2, \ldots, b_{\ceil{n/2}}\)）分成若干組，而每一組的數量都會滿足：把這組資料由右至左依序進行二分插入法，都是最不浪費資訊的。

我們現在來引用 Donald Knuth 《The Art of Computer Programming》裡面提到的分析技巧²：

這些組別分起來，會長得像這樣：\(\{b_1\}\)、\(\{b_2, b_3\}\)、\(\{b_4, b_5\}\)、\(\{b_6, b_7, b_8, b_9, b_{10}, b_{11}\}\)…。我們可以令 \(t_k\) 代表最大的註標使得把跟它分派到同一組的所有元素，依照反過來的順序依序二分插入序列時，最壞情形下每次都恰好需要 \(k\) 次比較。即，跟 \(t_0\) 同一組的資料插入序列恰好需要 0 次比較、跟 \(t_2\) 同一組的資料插入序列需要 2 次比較、依此類推。

要怎麼找出 \(t_k\) 的值呢？注意到，當 \(b_{t_k}\) 的筆資料被插入序列的時候，所有註標不超過 \(t_{k-1}\) 的資料已經被加入序列了。此外，所有註標等於 \(t_{k-1}+1, \ldots, t_k\) 的元素都還沒有被加入序列。也就是說，此時序列恰恰好有 \(2t_{k-1}+(t_k-t_{k-1}-1) = t_{k-1}+t_k-1\) 筆資料！（這個 \(-1\) 是因為最後一個註標 \(b_{t_k}\) 頭頂上那筆資料不需要被考慮進去，它的資料比所有人都來得大）為了讓資訊不浪費，我們希望 \(t_{k-1}+t_k-1 = 2^k-1\)。因此得到 \[ t_{k-1} + t_k = 2^k\text{。} \] 經過一番寒徹骨，不是，經過一翻兩瞪眼以後，不是，總之，經過一直翻一直翻，我們可以得出一個神奇的結論： \[ \begin{aligned} t_k &= 2^k - 2^{k-1} + 2^{k-2} - \cdots + (-1)^k2^0\\ &= (2^{k+1}+(-1)^k)/3. \end{aligned} \]

有了這個演算法以後，我們就可以利用遞迴方法來分析，這個合併插入排序需要的比較總次數了。我們令 \(F(n)\) 表示對 \(n\) 筆資料進行 Merge-Insertion Sort 最壞情形下所需要的比較次數。 那麼可以得到遞迴關係：

\[ F(n) = \floor{n/2} + F(\floor{n/2}) + G(\ceil{n/2}) \]

其中，\(G(\ceil{n/2})\) 表示著當牙刷刷毛有 \(\ceil{n/2}\) 根的時候（分別是 \(b_1, b_2, \ldots, b_{\ceil{n/2}}\)），要合併成一條單鏈需要的比較次數。藉由 \(\{t_i\}\) 的表示法，若 \(t_{k-1} < \ceil{n/2}\le t_k\)，我們可以把 \(G(\ceil{n/2})\) 寫成

\[ \begin{aligned} G(\ceil{n/2}) &= \sum_{i=1}^{k-1} i (t_i-t_{i-1}) + k(\ceil{n/2} - t_{k-1}) \\ &= k\ceil{n/2} - (t_0 + t_1 + \cdots + t_{k-1}) \end{aligned} \]

令 \(w_k = t_0+t_1+\cdots + t_{k-1} = \floor{2^{k+1}/3}\)。 現在來證明今天最重要的一個結論：

引理 22

\( F(n) - F(n-1) = k \) 若且唯若 \(w_k < n \le w_{k+1}\)。

證明

我們可以用數學歸納法。Base Case 很顯然，所以就不寫了。Inductive Case 的部分可以利用 \(n\) 的奇偶性分別討論：如果 \(n\) 是偶數，那麼 \(F(n)-F(n-1) = 1+F(n/2)-F(n/2-1)\)，後半部的數值等於 \(k-1\) 若且唯若 \(w_{k-1} < \floor{n/2} \le w_{k}\)。而由 \(w_k\) 之定義可知

\[ \begin{aligned} && w_{k-1} & < & n/2 & \le w_{k} & \text{（} n \text{ 是偶數。）}\\ &\Longleftrightarrow & \floor{2^{k}/3} & < & n/2 & \le \floor{2^{k+1}/3} \\ &\Longleftrightarrow & 2\floor{2^{k}/3} & < & n & \le 2\floor{2^{k+1}/3} \\ &\Longleftrightarrow & 2\floor{2^{k}/3}+1 & < & n & \le 2\floor{2^{k+1}/3} & \text{（} n \text{ 是偶數，這很重要。）} \\ &\Longrightarrow & \floor{2^{k+1}/3} & < & n & \le \floor{2^{k+2}/3} \\ \end{aligned} \]

於是 \(n\) 是偶數的時候結論成立。第二種情形，當 \(n\) 是奇數的時候，我們可以依樣畫葫蘆：

\[ F(n)-F(n-1) = G(\ceil{n/2})-G(\ceil{(n-1)/2}) \]

然後這個值是 \(k\) 若且唯若 \(t_{k-1} < \ceil{n/2} \le t_k\)，然後這個等價於 \(w_k < n\le w_{k+1}\)，得證。

有了引理 22 以後，我們試圖找出 \(k\) 與 \(n\) 之間的關係。因為 \(w_k < n \le w_{k+1}\)，所以 \(k\) 可以寫成 \(\ceil{\log_2 \frac{3}{4}n}\)。於是得到很酷的結論：

\[ F(n) = \sum_{i=1}^n \ceil{\log_2 \frac{3}{4}i} \approx n\log_2 n - 1.415n + O(\log_2 n) \]

還記得二分插入法的上界、以及資訊理論下界嗎？我們把它們同步列出來：

\[ A(n) = \ceil{\log n!} \approx n\log_2 n - 1.443 n + O(\log_2 n) \]

\[ B(n) = \sum_{i=1}^n \ceil{\log i} \approx n\log_2 n - 0.915 n + O(\log_2 n) \]

不難發現 \(F(n)\) 比起二分插入法得到的比較次數 \(B(n)\)，更接近資訊理論下界 \(A(n)\) 了呢！

結論

後話就是，在 1979 年 Manacher³ 用了混合方法，把 Hwang-Lin⁴ 的兩序列合併演算法考慮進去並且在某些情形下改良，同時改進了 Ford-Johnson 演算法，並且證明了存在無窮多個 \(n\)，其最少比較排序的比較次數比 \(F(n)\) 嚴格來得小，該方法贏過 FJ 的最小值是 \(n=189\)。然後到了 1985 年 Bui 和 Thanh⁵ 再次修改了 Manacher 演算法，得出在絕大多數的 \(n\) 時，FJ 演算法不是最優的。而且也得出了最小反例出現在 \(n=47\)（到 2007 年為止，Peczarski⁶ 聲稱 FJ 演算法在 \(n<47\) 的時候是最佳解，Peczarski 證明了利用某一類型的分而治之演算法無法在 \(n\le 46\) 的時候贏過 FJ 演算法。）

然後 \(F(n)\) 其實有封閉形式（Closed Form，俗稱公式解）： \[ F(n) = n\ceil{\log_2 \frac{3}{4} n} + \floor{\frac13 2^{\floor{\log_2 6n}}} + \floor{\frac12\log_2 6n}\text{。} \]

最後，大家要多多刷牙喔 ^_<。

合併插入排序法中間的分析，利用到了「如何從排序到一半的東西，利用盡量少比較次數完成排序」的特性。我們是否可以把這個概念推廣一下呢？排序到一半的東西，可以被表示成一個叫做 偏序集（Partial Ordered Set） 的東西。我們能否從偏序集獲得一些排序知識呢？

推薦閱讀

• 維基百科：https://en.wikipedia.org/wiki/Merge-insertion_sort
• Ford-Johnson 演算法當年的論文：https://www.jstor.org/stable/pdf/2308750.pdf