Merge sort 論文閱讀與見解

Introduction

閱讀 commit b5c56e0 提及之三篇論文並思考 merge sort 與其變形之優劣勢，並嘗試提示洞見與可能的改進。該 commit 提及的論文分別如下

• Bottom-up Mergesort: A Detailed Analysis
• The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules
• Queue-Mergesort

Bottom-up Mergesort

$C(N)$ 表示排序

$N$ 個元素最少需要做幾次比較，這項指標對排序演算法的效能影響最大。 Divide-and-conquer 演算法幾乎都存在週期性現象， merge sort 也不例外。該論文首先定義

$C_{b,td}(N),C_{w,td}(N),C_{a,td}(N)$ 這三個參數表示 top-down mergesort 在 best case, worst case 與 average case 所需要的比較次數。

$C_{w,td}(N)$ 還可以因為其週期性性質而歸納出以下公式

$$C_{w,td}(N)=N\cdot lg(N)+N\cdot A(lg(N))+1$$
其中

$A(x)=1-\{x\}-2^{1-\{x\}}$ ，因此上式展開後可得

$$C_{w,td}(N)=N\cdot lg(N)+N\cdot (1-lg(N)-2^{1-lg(N)})+1$$
不過我不理解此處為何能清楚展現 mergesort 的週期特性，同時對於 best case 來說

$$C_{b,td}(N)=\sum _{n<N}v(n)$$

$v(n)$ 即是

$n$ 的 population count ，這篇論文主要是想要推導出對於 bottom-up mergesort 的 closed form 公式，也就是

$C_{b,bu}(N),C_{w,bu}(N),C_{a,bu}(N)$ 。

Bottom-up mergesort 和 top-down mergesort 差別在於 splitting 的方法， bottom-up mergsort 採用的是 "power-of-two" splitting ，而 top-down mergesort 則是採用 "half-and-half" splitting ，這也造成呼叫合併的次數會不同，把 mergesort 視覺化可以發現 merging process 看起來像一棵樹，而 bottom-up mergesort 在第

$j$ 層 ( 0-index ，最底層是 0 ) 有

$\lfloor \frac{N}{2^{j+1}}\rfloor$ 個進行完整合併的節點，也就是將

$2^j$ 個元素與

$2^j$ 個元素進行合併，另外若

$Nmod{2}^{j+1}>2^j$ 則會多一個 incomplete merge 來合併

$2^j$ 個元素與

$Nmod{2}^j$ 個元素，總結來說對於

$N$ 個元素的 bottom-up mergesort 總共需要

$\sum _{i=0}^k\lfloor \frac{N}{2^i}\rfloor$ 個 complete merge 與

$popcount(N)-1$ 個 incomplete merge 。假設合併

$(n,m)$ 元素所需的比較次數表示為

$c_{n,m}$

$$min\{n,m\}\le c_{n,m}\le n+m-1$$
並且

$c_{n,m}=j$ 的機率為

$$\frac{{\displaystyle (\genfrac{}{}{0ex}{}{j-1}{n-1})}+{\displaystyle (\genfrac{}{}{0ex}{}{j-1}{m-1})}}{{\displaystyle (\genfrac{}{}{0ex}{}{n+m}{n})}}$$
因此

$c_{n,m}$ 的期望值為

$$E\{c_{n,m}^r\}=nm(\frac{1}{n+r}+\frac{1}{m+r})[n+m+1{]}^{r-1}$$
其中

$[x{]}^k=x(x+1)\cdots (x+k-1)$

首先推導 best case 也就是

$C_{b,bu}(N)$ ， best cases 發生在每個合併過程都是最佳也就是

$c_{n,m}=min\{n,m\}$ 時，因此對於 complete merge 來說總比較次數是

$\sum _{j=0}^{k-1}(2^j\lfloor \frac{N}{2^{j+1}}\rfloor )$ ，因為 complete merge 在第

$j$ 層進行

$\lfloor \frac{N}{2^{j+1}}\rfloor$ 次

$(2^j,2^j)$ 的合併，

$k=\lceil lg(N)\rceil$ 。然後進行

$\sum _{j=1}^k{b}_j(b_{j-1}\cdots b_1{b}_0{)}_2$ 次 incomplete merge ，總共會是

$C_{b,bu}(N)=\sum _{n<N}v(n)$ 。
同時根據 Trollope-Delange formula 可以得出

$$\sum _{n<N}v(n)=\frac{1}{2}\cdot N\cdot lg(N)+N\cdot F_0(lg(N))$$
因此可以推導出以下 （看不出如何推導的）

$$F_0(x)=\frac{1}{2^x}\sum _{j\ge 0}({\beta }_j-\frac{1}{2})(0\cdots 0{\beta }_{j+1}{\beta }_{j+2}\cdots {)}_2-\frac{x}{2}=\sum f_k{e}^{2\pi ikx}$$
將

$F_0(x)$ 做圖可看出他的週期特性。

worst case 則是每次

$(n,m)$合併都使用到

$(n+m-1)$ 次比較，可以推得

$C_{w,bu}(N)$ 為

$$N\cdot lg(N)+N[\frac{1}{N}\sum _{0<j\le k}(b_{j-1})(b_{j-1}{b}_{j-2}\cdots b_0)-\{lg(N)\}-\frac{2^{v_2(N)}}{N}]+1$$
其中

$v_2(N)$ 為 trailing zeros ，其中 linear term 是

$\frac{1}{N}\sum _{0<j\le k}(b_{j-1})(b_{j-1}{b}_{j-2}\cdots b_0)-\{lg(N)\}-\frac{2^{v_2(N)}}{N}$ 做圖後也可看出他的週期特性。
Average case 則是透過加總每個合併的比較次數期望值，同樣可以在 linear term 發現週期特性。

Bottom-up mergesort v.s. Top-down mergesort

兩者在 best case 當中比較次數會相同，但 worst case 和 average case 皆是 top-down mergesort 比較次數更少，並且可以證明 top-down mergesort 的 splitting strategy 使得它在 worst case 和 average case 上都表現得比其他 mergesort 變形更好。只有當

$N$ 為二的指數時， 兩種演算法在 worst case 上的表現才會相同。

Queue-mergesort

建構一個 queue 並且當中的元素都是排序好的鍵結串列，一開始每個節點都是一個串列， queue-mergesort 的演算法如下

while (Q.size > 1) {
    Q.put(Merge(Q.get, Q.get))
}

每次把 queue head 的前兩個元素取出並進行合併，把合併後的鍵結串列放入 queue tail ，不斷進行直到 queue 當中只有一個元素也就是剩一個鍵結串列。特別注意到在任何時間點， queue 當中鍵結串列的長度都是單調遞增的。
此論文嘗試證明 queue-mergesort 是 optimal mergesort ，而 optimal mergesort 的定義代表在排序任何數量

$n$ 個元素的情況下，該 mergesort 在 worst case 下的比較次數是最少，就代表該 mergesort 是 optimal mergesort 。
任何 mergesort 的過程都可以畫成一顆樹狀結構圖， top-down mergesort 每次把

$n$ 個元素拆成兩個集合大小分別是

$\lfloor \frac{n}{2}\rfloor$ 和

$\lceil \frac{n}{2}\rceil$ ， bottom-up mergesort 則是把每個元素當成單一鍵結串列來看待並兩兩合併，每個 leaf node 的權重是 1 代表只有一個元素，每個 internal node

$v$ 的權重是

$w(v)$ 同時也代表該節點代表的鍵結串列的元素數量，我們知道進行

$(m,n)$ 的合併 worst case 需要

$m+n-1$ 次比較，因此對於 internal node

$v$ 來說 worst case 需要

$w(v)-1$ 次比較，把整顆二元樹的內部節點權重加總即是該 mergesort 在 worst case 的比較次數總數

$$\sum _{v\in T}[w(v)-1]=[\sum _{v\in T}w(v)]-(n-1)$$
同時定義整棵樹的權重

$w(T)=\sum w(v)$ ，因此可以定義 optimal mergesort 代表

$w(T)\le w(T^{\prime })$ 。
如何證明 queue mergesort 是 optimal mergesort 呢？我們需要了解兩種特性

• $w(T)=E(T)$ ，其中
  $E(T)$ 代表樹
  $T$ 的 external path length ，假設
  $l$ 代表樹
  $T$ 的 leaf node ，則
  $h(l)$ 代表 root 和
  $l$ 的距離也就是邊數，因此
  $E(T)=\sum _{l}h(l)$ ，而我們又知道
  $w(T)=E(T)$ ，所以證明 optimal mergesort 可以轉化為找到 mergesort 的樹
  $T$ 滿足
  $E(T)\le E(T^{\prime })$ 。
• Huffman encoding
  此演算法可以建構出 weighted external path length 最小的 binary tree ，透過將 leaf node 透過他們的權重排序
  $w_1,w_2,\cdots ,w_n$ 後每次將最小的兩個節點拿出來合併，合併後的節點權重是
  $w_i+w_j$ 然後再插入回節點集合當中，不斷重複直到剩下一個元素。

不難看出 queue mergesort 就是所有 leaf node 權重皆為一的 Huffman encoding ，因此 queue mergesort 可以建構出一顆有最小 external path length 的 binary tree ，也證明了 queue mergesort 是 optimal mergesort 。

Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and power-of-2 Rules

不同版本 Merge Sort 的比較次數可以利用以下遞迴式來表達

$$f_n=f_{\tau (n)}+f_{n-\tau (n)}+g_n$$
其中

$g_n$ 代表合併的成本，並且

$\tau (n)$ 隨著不同的實作有不同的可能

• $\tau (n)=\lfloor \frac{n}{2}\rfloor$ ， top-down mergesort 版本
• $\tau (n)=2^{\lceil lo{g}_2(\frac{n}{2})\rceil }$ ， bottom-up mergesort ( max power-of-2 rule )
• $\tau (n)=2^{\lfloor lo{g}_2(\frac{2n}{3})\rfloor }$ ， queue-mergesort ( balanced power-of-2 rule )

特別注意在 balanced power-of-2 rule 當中只有選擇

$2^{lo{g}_2(\frac{2n}{3})}$ 是平衡的，它是一個介於

$n/3$ 和

$2n/3$ 之間的二的冪次方數。雖然 Queue Mergesort 剛好符合 Heap recurrence 也就是

$f_n=mi{n}_{1\le j\le n}(f_j+f_{n-j})+g_n$ 的解，並且實作上不需要事先知道要排序的 input size ，非常適合用在鍵結串列上，但我們付出的代價是它並非 stable sort 。

以下分析中會使用的符號如下

• $\rho =min(2^{\lfloor lo{g}_2(\frac{2n}{3})\rfloor },n-2^{\lfloor lo{g}_2(\frac{2n}{3})\rfloor })$
• $\lambda =n-\rho$

Lemma 1. The cost of QM is described by the heap recurrence

$$f_n=f_{\lambda }+f_{\rho }+g_n$$

證明方法和 Huffman code 過程一樣，設定在第 i 次迴圈時 queue 當中元素大小為

$a_{i,i}\le a_{i,i+1}\le a_{i,i+2},\cdots ,a_{i,n}$ ，一開始

$a_{1,j}=1,\mathrm{\forall }j$ ，最後

$a_{n,n}=n$ 。
每個迴圈過程

$(a_{i,i},\cdots ,a_{i,n})$ 會轉變為

$(a_{i+1,i+1},\cdots ,a_{i+1,n})$ ，並且

$a_{i+1,j}=a_{i,j+1}$ ，

$a_{i+1,n}=a_{i,i}+a_{i,i+1}$ ，並保有以下 loop invariance

• 存在整數
  $k$ 使得
  $2^k\le a_{i,j}\le 2^{k+1}$
• $\mathrm{\forall }j=\{i,\cdots ,n-1\},\frac{1}{2}\le \frac{a_{i,j}}{a_{i,j+1}}\le 1$
• 最多一個
  $a_{i,j}$ 不是二的冪

Lemma 2. The solution of

$f_n$ of the heap recurrence with

$f_1=g_1$ is

$$f_n=\sum _{j=1}^L(\lfloor \frac{n}{2^{j-1}}\rfloor -\lfloor \frac{n}{2^j}\rfloor -1)g_{2^j}+\sum _{j=0}^L{g}_{n_j}$$

證明:
原本的 heap recurrence 可以寫為

$$f_n=f_{n_{L-1}}+f_{2^{L-1}}+g_{n_L}+b_{L-2}(f_{2^{L-2}}+g_{2^{L-1}})+b_{L-1}(f_{2^{L-1}}+g_{2^L})$$

透過歸納法可得

$$f_n=\sum _{j=0}^{L-1}(1+b_j)f_{2^j}+\sum _{j=1}^L{b}_{j-1}{g}_{2^j}+\sum _{j=0}^L{g}_{n_j}$$
最後把

$b_j=\lfloor \frac{n}{2^j}\rfloor -2\lfloor \frac{n}{2^{j+1}}\rfloor$ 帶入即可得證。

Lemma 3. Assume that

$f_n$ satisfies the heap recurrence. Then

$f_n/n\to l<\mathrm{\infty }$ iff

$g_n=o(n)$ and

$\sum _{j\ge 0}\frac{g_{2^j}}{2^j}=l$

Lemma 4. If

$f_n$ satisfies the heap recurrence and

$g_n=O(1)$, then

$f_n=\sum _{j\ge 0}\frac{g_{2^j}}{2^j}\cdot n+O(log(n))$

以上兩個定理可以歸納出 power-of-2 rule 的一個優點，假設

$g_n=O(n/log(n)),n\ne 2^L$ 且

$g_{2^L}=O(2^L/L^{1+\epsilon })$ ，則

$f_n=O(n)$ ，但如果把這組合併的 cost

$g_n$ 套用在 half-half rule 上，則

$f_n=O(nlog(n)log(n))$
如此一來我們可以推論，若合併的時間複雜度是

$o(n)$ ，此時若我們可以把輸入大小

$n$ 擴展到二的冪，則整體時間複雜度可以維持限性。

The analysis of queue-mergesort

假設有兩個排序好的序列，元素數量分別是

$x,y$ ，則合併它們的代價如下

• Best case :
  $min(x,y)$
• Worst case :
  $x+y-1$
• Average case :
  $u(x,y)=x+y-\frac{x}{y+1}-\frac{y}{x+1}$
• Variance case :
  $v(x,y)=\frac{x(2x+y)}{(y+1)(y+2)}+\frac{y(2y+x)}{(x+1)(x+2)}-(\frac{x}{y+1}+\frac{y}{x+1}{)}^2$

Worst case
假設 Queue mergesort 在 worst case 的總比較次數會是

$W_n$ 且

$W_1=0$ ，

$W_n=W_{\rho }+W_{\lambda }+n-1$ 。我們可以推得

$$W_n=n\cdot lo{g}_2(n)+n\cdot A(lo{g}_2(n))+1$$
而

$A(t)$ 是一個連續的週期性函數，週期為 1

$$A(t)=1-\{t\}-2^{1-\{t\}}$$
平均值是

$\frac{1}{2}-\frac{1}{log(2)}$ ，並且透過推導可得

$W_n=\sum _{j=1}^n\lceil lo{g}_2(j)\rceil$ ，可以推斷若 dividing rule 滿足

$n\to (j,n-j),\rho \le j\le \lfloor \frac{n}{2}\rfloor$ ，則它是 worst case optimal 。所以 Top-down Mergesort 和 Queue Mergesort 是 optimal mergesorts 的邊界。

此處看不懂為何這樣的 diving rule 就是 worst case optimal

Best case
假設 Best case 的成本是

$B_n$ ，合併成本

$g_n$ 為以下

$$g_n=min(\lambda ,\rho )=\rho =\{\begin{array}{l}{2}^{L-1},if{b}_{L-1}=0\\ 2^L(\frac{n}{2^L})=n-2^L,if{b}_{L-1}=1\end{array}$$

$B_n$ 則是可推得

$$B_n=\{\begin{array}{l}{B}_{2n}=2B_n+n\\ B_{2n+1}=B_n+B_{n+1}+n\end{array}$$
可得

$B_n=\sum _{j=0}^{n}v(j)$ ，其中

$v(j)$ 代表

$j$ 的二進位表示法的 sum-of-digits ，推得以下。

$$B_n=\frac{1}{2}n\cdot lo{g}_2(n)+n\cdot D(lo{g}_2(n))$$

Average case
假設 n 個元素的

$n!$ 種排列方式出現的機率完全相同，用

$X_n$ 代表隨機排列下 Queue Mergesort 所需的比較次數

Theorem 1. The average number of comparisons used by QM to sort a random permutation of n elements
滿足

$$U_n=E(X_n)=nlo{g}_2(n)+(A(lo{g}_2(n))-\alpha )n+4\varpi (lo{g}_2(n))+O(1)$$
其中

$\alpha \approx 0.26449978$ ，

$\varpi (u)$ 在

$O(u),\mathrm{\Omega }(u)$ 之間震盪

$$\varpi (u)=\sum _{j=0}^{\lfloor j\rfloor }\frac{(\{2^{u-j}\}-\{2^{u-j-1}\}{)}^2}{(1+\{2^{u-j}\}(1-\{2^{u-j}\}+2\{2^{u-j-1}\}))}$$

Asymptotic Normality

假設

$P_n(z)$ 是

$X_n$ 的 probability generating function ，則

$P_n(z)$ 滿足

$$\{\begin{array}{l}{P}_n(z)=P_{\lambda }(z)P_{\rho }(z)Q_n(z)\\ P_1(z)=1\end{array}$$
假設

$Y_n$ 是 two-way linear merge algorithm for mergin two sorted files of sizes

$\rho ,\lambda$ ，且

$Q_n(z)$ 是它的 probability generating function ，則

$$Q_n(z)=E(z^{Y_n})=\sum _{k=1}^{\lambda }\frac{{\displaystyle (\genfrac{}{}{0ex}{}{n-k-1}{\rho -1})}+{\displaystyle (\genfrac{}{}{0ex}{}{n-k-1}{\lambda -1})}}{{\displaystyle (\genfrac{}{}{0ex}{}{n}{\lambda })}}{z}^{n-k}$$

Theorem 3. The distribution function of the random variable

$X_n$ is asymptotically normal

$$F_n(x)=\mathrm{\Phi }(x)+O(\frac{log(n)}{\sqrt{n}})$$

Invariance Principle for power-of-2 recurrence

$$f_n=f_{2^{\lfloor lo{g}_2(\theta n)\rfloor }}+f_{n-2^{\lfloor lo{g}_2(\theta n)\rfloor }}+g_n$$
其中

$\frac{1}{2}\le \theta <1$ ，所以

$\theta =\frac{2}{3}$ 並非特別的數字。

Invariance principle
假設

$f_n$ 滿足上述遞迴式，且

$\frac{1}{2}\le \theta <1$ ，則

$\frac{f_n}{n}\to l<\mathrm{\infty }$ iff

$g_n=o(n)$ 且

$\sum _{j\ge 0}\frac{g_{2^j}}{2^j}=l$

對於將 floor function 替換成 ceil function ，同樣的結論也適用，而此時

$\frac{1}{4}<\theta \le \frac{1}{2}$ 。

Lemma 8. if

$g_n=O(1)$ then the solution to the recurrence satisfies

$f_n=ln+O(log(n)),wherel=\sum _{j\ge 0}\frac{g_{2^j}}{2^j}$

Optimal Mergesorts

Average case
我們要找到滿足下列遞迴式並使其最小化的 index

$$U(n)=mi{n}_{1\le j\le n-1}\{U(j)+U(n-j)+u(j,n-j)\}$$
目標是找到 j 使得

$U(n)$ 最小化，結果會是

$j=\lfloor \frac{n}{2}\rfloor$ 是最佳解，也就是發生在 top-down mergesort 時。

Variance

$$V(n)=mi{n}_{1\le j\le n-1}\{V(j)+V(n-j)+v(j,n-j)\}$$
我們可以透過證明

$V(n)=\beta n+O(log(n))$ ，代表 queue mergesort 的 variance 是 asymptotically minimal 。