Merge sort 論文閱讀與見解

# Merge sort 論文閱讀與見解 ## Introduction 閱讀 [commit b5c56e0](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 提及之三篇論文並思考 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 \cfrac{N}{2^{j+1}} \rfloor$ 個進行完整合併的節點，也就是將 $2^j$ 個元素與 $2^j$ 個元素進行合併，另外若 $N \ \ mod \ \ 2^{j+1} > 2^j$ 則會多一個 incomplete merge 來合併 $2^j$ 個元素與 $N \ \ mod \ \ 2^j$ 個元素，總結來說對於 $N$ 個元素的 bottom-up mergesort 總共需要 $\sum_{i=0}^{k} \lfloor \cfrac{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$ 的機率為 $$ \cfrac{\dbinom{j-1}{n-1} + \dbinom{j-1}{m-1}}{\dbinom{n+m}{n}} $$ 因此 $c_{n,m}$ 的期望值為 $$ E\{c_{n,m}^{r}\} = nm(\cfrac{1}{n+r} + \cfrac{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 \cfrac{N}{2^{j+1}} \rfloor)$ ，因為 complete merge 在第 $j$ 層進行 $\lfloor \cfrac{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_1b_0)_2$ 次 incomplete merge ，總共會是$C_{b, bu}(N) = \sum_{n<N}v(n)$ 。同時根據 Trollope-Delange formula 可以得出 $$ \sum_{n<N}v(n) = \cfrac{1}{2} \cdot N\cdot lg(N) + N\cdot F_0(lg(N)) $$ 因此可以推導出以下（看不出如何推導的） $$ F_0(x) = \cfrac{1}{2^x} \sum_{j \ge 0} (\beta_j - \cfrac{1}{2})(0\cdots 0 \beta_{j+1}\beta_{j+2}\cdots)_2 - \cfrac{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[\cfrac{1}{N}\sum_{0<j\le k}(b_{j-1})(b_{j-1}b_{j-2}\cdots b_0) - \{lg(N)\} - \cfrac{2^{v_2(N)}}{N}] + 1 $$ 其中 $v_2(N)$ 為 trailing zeros ，其中 linear term 是 $\cfrac{1}{N}\sum_{0<j\le k}(b_{j-1})(b_{j-1}b_{j-2}\cdots b_0) - \{lg(N)\} - \cfrac{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 \cfrac{n}{2} \rfloor$ 和 $\lceil \cfrac{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')$ 。如何證明 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')$ 。 * **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 \cfrac{n}{2} \rfloor$ ， top-down mergesort 版本 * $\tau (n) = 2^{\lceil log_2(\frac{n}{2}) \rceil}$ ， bottom-up mergesort ( max power-of-2 rule ) * $\tau (n) = 2^{\lfloor log_2(\frac{2n}{3}) \rfloor}$ ， queue-mergesort ( balanced power-of-2 rule ) 特別注意在 balanced power-of-2 rule 當中只有選擇 $2^{log_2(\frac{2n}{3})}$ 是平衡的，它是一個介於 $n/3$ 和 $2n/3$ 之間的二的冪次方數。雖然 Queue Mergesort 剛好符合 Heap recurrence 也就是 $f_n = min_{1\le j \le n}(f_j + f_{n-j}) + g_n$ 的解，並且實作上不需要事先知道要排序的 input size ，非常適合用在鍵結串列上，但我們付出的代價是它並非 stable sort 。以下分析中會使用的符號如下 * $\rho = min(2^{\lfloor log_2(\frac{2n}{3}) \rfloor}, n - 2^{\lfloor log_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, \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}$ * $\forall j = \{i, \cdots, n-1 \} , \cfrac{1}{2} \le \cfrac{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 \cfrac{n}{2^{j-1}} \rfloor - \lfloor \cfrac{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 \cfrac{n}{2^j} \rfloor - 2 \lfloor \cfrac{n}{2^{j+1}} \rfloor$ 帶入即可得證。 **Lemma 3. Assume that $f_n$ satisfies the heap recurrence. Then $f_n/n \rightarrow l < \infty$ iff $g_n = o(n)$ and $\sum_{j\ge 0} \cfrac{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}\cfrac{g_{2^j}}{2^j} \cdot n + O(log(n))$** 以上兩個定理可以歸納出 power-of-2 rule 的一個優點，假設 $g_n = O(n/log(n)) , n \neq 2^L$ 且 $g_{2^L} = O(2^L/L^{1+\varepsilon})$ ，則 $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 - \cfrac{x}{y+1} - \cfrac{y}{x+1}$ * Variance case : $v(x, y) = \cfrac{x(2x+y)}{(y+1)(y+2)} + \cfrac{y(2y+x)}{(x+1)(x+2)} - (\cfrac{x}{y+1} + \cfrac{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 log_2(n) + n\cdot A(log_2(n)) + 1 $$ 而 $A(t)$ 是一個連續的週期性函數，週期為 1 $$ A(t) = 1 - \{t\} - 2^{1 - \{t\}} $$ 平均值是 $\cfrac{1}{2} - \cfrac{1}{log(2)}$ ，並且透過推導可得 $W_n = \sum_{j=1}^{n} \lceil log_2(j) \rceil$ ，可以推斷若 dividing rule 滿足 $n \rightarrow (j, n-j), \rho \le j \le \lfloor \cfrac{n}{2} \rfloor$ ，則它是 worst case optimal 。所以 Top-down Mergesort 和 Queue Mergesort 是 optimal mergesorts 的邊界。 :::warning 此處看不懂為何這樣的 diving rule 就是 worst case optimal ::: **Best case** 假設 Best case 的成本是 $B_n$ ，合併成本 $g_n$ 為以下 $$ g_n = min(\lambda, \rho) = \rho = \begin{cases} 2^{L-1} , if \ \ b_{L-1}=0\\ 2^L(\cfrac{n}{2^L}) = n - 2^L , \ \ if \ \ b_{L-1}=1\\ \end{cases} $$ $B_n$ 則是可推得 $$ B_n = \begin{cases} B_{2n} = 2B_n + n\\ B_{2n+1} = B_n + B_{n+1} + n\\ \end{cases} $$ 可得 $B_n = \sum_{j=0}^{n} v(j)$ ，其中 $v(j)$ 代表 $j$ 的二進位表示法的 sum-of-digits ，推得以下。 $$ B_n = \cfrac{1}{2}n \cdot log_2(n) + n \cdot D(log_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) = nlog_2(n) + (A(log_2(n)) - \alpha)n + 4 \varpi (log_2(n)) + O(1) $$ 其中 $\alpha \approx 0.26449978$ ， $\varpi(u)$ 在 $O(u), \Omega(u)$ 之間震盪 $$ \varpi(u) = \sum_{j=0}^{\lfloor j \rfloor} \cfrac{(\{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{cases} P_n(z) = P_{\lambda}(z)P_{\rho}(z)Q_n(z)\\ P_1(z) = 1 \end{cases} $$ 假設 $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} \cfrac{\dbinom{n-k-1}{\rho -1} + \dbinom{n-k-1}{\lambda -1}}{\dbinom{n}{\lambda}} z^{n-k} $$ **Theorem 3. The distribution function of the random variable $X_n$ is asymptotically normal** $$ F_n(x) = \Phi (x) + O(\cfrac{log(n)}{\sqrt{n}}) $$ ### Invariance Principle for power-of-2 recurrence $$ f_n = f_{2^{\lfloor log_2(\theta n) \rfloor}} + f_{n - 2^{\lfloor log_2(\theta n) \rfloor}} + g_n $$ 其中 $\cfrac{1}{2} \le \theta < 1$ ，所以 $\theta = \cfrac{2}{3}$ 並非特別的數字。 **Invariance principle** 假設 $f_n$ 滿足上述遞迴式，且 $\cfrac{1}{2} \le \theta < 1$ ，則 $\cfrac{f_n}{n} \rightarrow l < \infty$ iff $g_n = o(n)$ 且 $\sum_{j\ge 0} \cfrac{g_{2^j}}{2^j} = l$ 對於將 floor function 替換成 ceil function ，同樣的結論也適用，而此時 $\cfrac{1}{4} < \theta \le \cfrac{1}{2}$ 。 **Lemma 8. if $g_n = O(1)$ then the solution to the recurrence satisfies $f_n = ln + O(log(n)) , where \ \ l = \sum_{j\ge 0}\cfrac{g_{2^j}}{2^j}$** ### Optimal Mergesorts **Average case** 我們要找到滿足下列遞迴式並使其最小化的 index $$ U(n) = min_{1\le j \le n-1} \{U(j) + U(n-j) + u(j, n-j)\} $$ 目標是找到 j 使得 $U(n)$ 最小化，結果會是 $j = \lfloor \cfrac{n}{2} \rfloor$ 是最佳解，也就是發生在 top-down mergesort 時。 **Variance** $$ V(n) = min_{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 。