以下部分節錄自 [研讀 list_sort + 論文](https://hackmd.io/@devaraja/paper)

# The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules

主角 Queue-mergesort：一種最壞情況下最優的 mergesort 變體。

merge sort 通常是排序鏈結串列的首選方法。它是一個典型的 divide-and-conquer 例子，並且有幾種變體：
1. Top-down mergesort
**half-half rule**
$$\tau(n) = \lfloor n / 2 \rfloor$$
3. Bottom-up mergesort
**power-of-2 rule**
$$\tau(n) = 2^{\lfloor \log_2 (n / 2) \rfloor}$$
5. Queue-mergesort
**balanced power-of-2 rule**
$$\tau(n) = 2^{\lfloor \log_2 (2n / 3) \rfloor}$$

這裡的 $\tau(n)$ 表示在分割大小為 n 的問題時，第一個子問題的大小。

論文指出，$2^{\lfloor \log_2 (2n / 3) \rfloor}$ 是唯一一個位於 $n/3$ 和 $2n/3$ 之間的 2 的冪，選擇其他比例不會更平衡。後面應該會有證明來說明。

## 二、Queue mergesort & heap recurrence
> 以下都簡稱 queue mergesort 為 QM

QM 的基本運作方式：
1. 開始時，每個元素各自在一個鏈結串列中，並將這些鏈結串列串成一個佇列
2. 取出佇列的前兩個鏈結串列，使用線性的 mergesort 將它們合併
3. 將合併後的新鏈結串列放入佇列的尾部
4. 重複上述步驟，直到佇列中只剩下一個鏈結串列（此時所有元素已排序完成）

> 問：lab0-c 的結構是不是反過來啊？

從以上圖片可以看出：QM 演算法有個問題，他不會是 stable sorting，因為他的行為會是一直把合併排序好的鏈結串列放到佇列的尾巴。

>From a practical viewpoint, QM is easily implemented on linked list, its
code being simpler than those of TDM and BUM. Also the size of the input need not be known in advance and it can be implemented in either a top-down or a bottom-up manner, making QM an attractive alternative to TDM and BUM. The price we pay is stability: QM is not stable for equal keys.

:::info
但是 list sort 的方式解決了 QM 沒有 stable sorting 的問題
:::

論文證明了 **QM 可以用一種 top-down 的方式**實現，這對排序鏈結串列很適合；分割策略就是 balanced power-of-2 rule。

### LEMMA 1
根據方才說明的 bottom-up QM 演算法進行以下證明。
**首先，定義 heap recurrence。** QM 的成本可以通過 heap recurrence 來描述：
$$f_n = f_\lambda + f_\rho + g_n, \quad n \geq 2$$
其中：
* $g_n$ 表示合併成本
* $\rho = \min \left\{ 2^{\lfloor \log_2 (2n / 3) \rfloor}, \, n - 2^{\lfloor \log_2 (2n / 3) \rfloor} \right\}$ ，即兩個子問題中較小的那個
* $\lambda = n-ρ$，即較大的子問題
* $2^{\lfloor \log_2 (2n / 3) \rfloor}$ 是唯一一個在 $\frac{n}{3}$ 和 $\frac{2n}{3}$ 之間的 2 的冪

**第二，分析佇列中的鏈結串列大小：**

用 $a_{i,j}$ 表示在演算法第 $i$ 次迭代時，佇列中第 $j$ 個位置上的鏈結串列大小。
這些 $a_{i,j}$ 值滿足以下條件：
$$a_{i,i} ≤ a_{i,i+1} ≤ ... ≤ a_{i,n}$$
因為是每次合併排序前兩個鏈結串列再移動到佇列的尾端，所以可以得知每個鏈結串列的大小會越來越大。

* 初始狀態下（i = 1）：
每個元素各自為一個鏈結串列，所以 $a_{1,j} = 1，j = 1, ..., n$
* 最終狀態（i = n）：
佇列中只剩一個鏈結串列，包含所有元素，所以 $a_{n,n} = n$

**第三，分析迭代過程中列表大小的變化：**

QM 在每次迭代中，將 $(a_{i,i}, ..., a_{i,n})$ 轉換為 $(a_{i+1,i+1}, ..., a_{i+1,n})$，其中 $a_{i+1,j} = a_{i,j+1}（j = i+1, ..., n-1)$ 且 $a_{i+1,n} = a_{i,i} + a_{i,i+1}$ 。

以下圖示說明：
以論文中的 "sorting" 為例，所以 n 為 7。
i = 1 時：

digraph LinkedList {
    rankdir=LR;
    node [shape=record];

    s [label="s"];
    o [label="o"];
    r [label="r"];
    t [label="t"];
    i [label="i"];
    n [label="n"];
    g [label="g"];

    s -> o -> r -> t -> i -> n -> g;
}

此時 $a_{1,1}$ 到 $a_{1,7}$ 都是 1。
i = 2 時

digraph LinkedList {
    rankdir=LR;
    node [shape=record];
    r [label="r"];
    t [label="t"];
    i [label="i"];
    n [label="n"];
    g [label="g"];
    os [label="os"];

    r -> t -> i -> n -> g -> os;
}

此時變成 $a_{2,2}$ 到 $a_{2,7}$。
$a_{2,j} = a_{1,j+1}（j = i+1, ..., 6)$，這是因為每次迭代都會往前推進兩個鏈結串列元素。
$a_{2,7} = a_{1,1} + a_{1,2}$，這是因為新的佇列的最後一個鏈結串列即為原本的前面兩個鏈結串列的合併結果。

digraph LinkedList {
    rankdir=LR;  
    node [shape=record];
    s [label="s", fillcolor=lightyellow, style=filled];
    o [label="o", fillcolor=lightyellow, style=filled];
    r1 [label="r"];
    t [label="t"];
    i [label="i"];
    n [label="n"];
    g1 [label="g"];

    s -> o -> r1 -> t -> i -> n -> g1;

    r2 [label="r"];
    t2 [label="t"];
    i2 [label="i"];
    n2 [label="n"];
    g2 [label="g"];
    os [label="os", fillcolor=lightyellow, style=filled];

    r2 -> t2 -> i2 -> n2 -> g2 -> os;

    r2 -> r1 [color=red]; 
    t2 -> t[color=red];
    i2 -> i[color=red];
    n2 -> n[color=red];
    g2 -> g1[color=red];
}

註：紅色的箭頭不是指標！只是用來表達 $a_{2,j} = a_{1,j+1}$


透過歸納法，可以證明 $a_{i,j}$ 滿足以下性質：
1. 存在整數 $k$，使得 $2^k ≤ a_{i,j} ≤ 2^{k+1}，j = i, ..., n$
2. $1/2 ≤ a_{i,j}/a_{i,j+1} ≤ 1，j = i, ..., n-1$
* 每個佇列裡面的元素（鏈結串列）的下一個元素的大小，一定不是跟自己一樣大，就是自己的兩倍大以下。
* 由 $a_{i,j} ≤ a_{i,j+1} ≤ 2a_{i,j}，j = i, ..., n-1$ 推導
3. 在固定的 $i$ 時，最多有一個 $a_{i,j}$ 不是 2 的冪
* 大部分鏈結串列的大小都是 2 的冪（即 1, 2, 4, 8, 16, 32...等數值），最多只有一個鏈結串列的大小不是 2 的冪。
* 這是因為每次迭代只會發生一次鏈結串列的合併行為，而且合併之後的長度不是兩個相等的 2 的冪相加，就是兩個不相等的 2 的冪相加，或是 2 的冪與不是 2 的冪相加。
* 如果是兩個不相等的 2 的冪或是 2 的冪與不是 2 的冪相加，長度就不會是 2 的冪

:::info
list sort 也符合以上三種性質
:::


每次進行合併操作（將前兩個鏈結串列合併後放到佇列尾部）後，新的佇列狀態仍然滿足以上三個性質。

**第四，分析最終狀態前的佇列：**
在第 n-1 次迭代後（即最後一次合併前），佇列中只剩下兩個鏈結串列，分別是 $a_{n-1,n-1}$ 和 $a_{n-1,n}$，可以推論這兩個鏈結串列：
* 會在最後一次迭代中合併成最終排序好的佇列
* 大小之和必須等於 n
* 大小必須滿足前面證明的性質

而一開始定義的 $\rho$ 和 $\lambda$ 正是在滿足「一個是 2 的冪」且「兩者之和為 n 」的條件下最平衡的分割
（根據 $\rho$ 的定義，$2^{\lfloor \log_2 (2n / 3) \rfloor}$ 是唯一一個在 $\frac{n}{3}$ 和 $\frac{2n}{3}$ 之間的 2 的冪），因此我們可以推論出 $a_{n-1,n-1} = \rho$ 且 $a_{n-1,n} = \lambda$。

:::info
直觀的理解是，QM 總是選擇最小的兩個鏈結串列合併，這自然會形成一種平衡，使得最終剩下的兩個鏈結串列的大小盡可能接近。

最終，當佇列中只剩下兩個鏈結串列時， $\rho$ 和 $\lambda$，而這也正是使用 $\rho = 2^{\lfloor \log_2 (2n / 3) \rfloor}$ 規則進行 top-down 分割得到的結果。

所以，雖然 QM 的實作是 bottom-up 的，但行為模式可以用 top-down 的 balanced power-of-2 rule 分割方式來描述。
:::

### LEMMA 2
描述了 heap recurrence 的解：
$$
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}
$$
其中：
$L = \lfloor\log_2 n\rfloor$

### LEMMA 3

## 三、Analysis of queue mergesort
討論 QM 在不同情況下的成本（指比較次數）。同時也將 QM 與 TDM 和 BUM 進行比較。
可以看到對於 average case，TDM 的成本是最低的，這點在第六章會有證明。
此外，QM 在 worst case 下會是最優的

定義合併兩個大小分別為 $x$ 和 $y$ 的已排序元素時，合併的成本：
Best case：
$$\min \{x, y\}$$
代表其中一個元素的值全部小於另一個元素。
Worst case：
$$x+y-1$$
代表兩個元素裡面的值是交錯的。
Average case：
$$x + y - \frac{x}{y+1} - \frac{y}{x+1}$$

論文指出，根據 Hammersley 和 Grimmett 的研究結果，任何使用 two-way linear 合併的 mergesort，如果切割結果在每個遞迴階段都滿足 $r ≤ j ≤ \frac{n}{2}$，那麼它在最壞情況下都是最優的。
$r ≤ j ≤ \frac{n}{2}$ 是一個條件：
* $r$ 在 QM 中是指 $2^{\lfloor \log_2 (2n / 3) \rfloor}$，即不超過 $\frac{2n}{3}$ 的最大 2 的冪
* $\frac{n}{2}$ 是傳統上 TDM 所採用的切割點

換句話說，只要切割點不要選得太小（至少要 $≥ r$），也不要超過中點（$≤ \frac{n}{2}$），那麼這個 mergesort 在最壞情況下就會是最優的。

:::info
觀察佇列中鏈結串列的大小，會發現一個規律：在任何時刻，佇列中的鏈結串列大小差異不大，並且大多數是 2 的冪。論文證明了這種方法等同於使用 balanced power-of-2 rule 規則進行分割。可以去看 Lemma 1
:::

至於 variance：論文證明 QM 的 variance 是 asymptotically optimal，且為線性增長，常數約為 0.3073，比 TDM 的 variance 小，而且不像 TDM 有週期性振盪。BUM 的 variance 則為 $O(n²)$，遠大於 QM 和 TDM。

:::info
第四章證明其 asymptotic normality
第六章證明其 asymptotically optimal
:::
## 四、Asymptotic normality
當樣本大小趨近於無限大時，某個統計量或隨機變數的分佈會趨近於常態分佈（也稱為高斯分佈）。

證明以下：
當 n（待排序的元素數量）趨近於無限大時，$Xn$（QM 對隨機排列進行排序所需的比較次數）的標準化結果：
$$(X_n - m_n)/s_n$$
這個分佈會收斂到標準常態分佈 $N(0,1)$，其中 $m_n$ 是 $X_n$ 的期望值，$s_n$ 是其標準差。
論文使用 characteristic function 和 Berry-Esseen 不等式來證明 QM 的 asymptotic normality。
> todo

### QM 符合 Asymptotic normality 有什麼意義？
1. 成本分佈更加穩定和可預測的優勢：
由於 QM 的成本分佈漸近於常態分佈，代表性能可以使用常態分佈的統計特性來預測。例如，可以預期約 95% 的排序操作會落在平均值 ± 2 個標準差的範圍內。
>The cost of QM satisfies actually a local limit theorem.

## 六、Optimal mergesorts
這個章節在討論 average 和 variance cases 下的 optimal mergesorts。

### Theorem 5
Average Case 下的最優合併排序是在每個遞迴階段盡可能平均的切割。也就是說，TDM 透過選擇j = ⌊n/2⌋在平均情況下是最優的，它會有最少的比較次數。

**Proof. 歸納法**

$U(n)$ 代表對大小為 n 的輸入進行 mergesort 時的平均比較次數
$U(1) = 0$（基本情況）
$U(n) = \min \{ U(j) + U(n-j) + u(j, n-j) \}, \quad n \geq 2, \quad 1 \leq j \leq n-1$

其中 $u(x,y)$ 是合併兩個已排序元素的平均比較次數，定義為：
$$u(x, y) = x + y - \frac{x}{y+1} - \frac{y}{x+1}$$
我們需要證明：對於任何 $n≥2$，$U(n)$ 的最小值會在 $j = ⌊\frac{n}{2}⌋$ 出現，即為切一半。

基礎情況：
當 $n = 2$ 或 $n = 3$ 時，結論顯然成立：
* 對於 $n = 2$，只有 $j = 1$ 這一種選擇
* 對於 $n = 3$，$j = 1$，平均切割是選擇 $j = 1$（因為 $⌊\frac{3}{2}⌋ = 1$ ）

歸納假設:
假設對於所有小於 $n$ 的正整數 $k$ ，最好的分割點是 $j = ⌊\frac{k}{2}⌋$。

需要證明對於 $n≥4$ ，當 $1 ≤ j < ⌊\frac{n}{2}⌋$ 時：
$$D=U(j)+U(n−j)+u(j,n−j)−U(⌊\frac{n}{2}⌋)−U(⌈\frac{n}{2}⌉)−u(⌊\frac{n}{2}⌋,⌈\frac{n}{2}⌉)>0$$

1. 根據歸納假設，可以將 $U(j)$ 和 $U(n-j)$ 展開：

$$U(j)=U(⌊\frac{j}{2}⌋)+U(⌈\frac{j}{2}⌉)+u(⌊\frac{j}{2}⌋,⌈\frac{j}{2}⌉)$$

$$U(n−j)=U(⌊\frac{n-j}{2}⌋)+U(⌈\frac{n-j}{2}⌉)+u(⌊\frac{n-j}{2}⌋,⌈\frac{n-j}{2}⌉)$$

2. 考慮兩種情況：
情況1：如果 $j$ 或 $n-j$ 為偶數
則：
$$⌊\frac{j}{2}⌋+⌊\frac{n−j}{2}⌋=⌊n/2⌋$$
$$⌈\frac{j}{2}⌉+⌈\frac{n−j}{2}⌉=⌈n/2⌉$$
將展開代入D中，可以得到：
$$D=u(⌊\frac{j}{2}⌋,⌈\frac{j}{2}⌉)+u(⌊\frac{n-j}{2}⌋,⌈\frac{n-j}{2}⌉)−u(⌊\frac{j}{2}⌋,⌊\frac{n-j}{2}⌋)−u(⌈\frac{j}{2}⌉,⌈\frac{n-j}{2}⌉)+u(j,n−j)−u(⌊\frac{n}{2}⌋,⌈\frac{n}{2}⌉)$$
經過代數變換，對於任意 $x$, $y$, $z$, $w$：
$$u(x,y) + u(z,w) - u(x,z) - u(y,w) + u(x+y,z+w) - u(x+z, y+w)$$
使用一開始提及的 $u(x,y)$ 可以展開為：
$$
(z-y)(w-x) \times \{\frac{1}{(y+1)(z+1)} + \frac{1}{(x+1)(w+1)} - \frac{(x+y+z+w+2)(x+y+z+w+1)}{(x+y+1)(x+z+1)(y+w+1)(z+w+1)}\}
$$
已知 $1 ≤ j < ⌊\frac{n}{2}⌋$，推知 $w > x$ ，$z > y$，因此 $(z-y)(w-x)$ 恆為正。
對於大括號內第三項的內容，比較分子分母的增長速度：
* 分子是兩個連續整數的乘積，因此它的增長速度是平方級別 $O(n^2)$
* 分母是四個項的乘積，其中每個括號內的值都與變數相關。考慮 $z>y$ 和 $w>x$ 時：
* $x+z+1>x+y+1$
* $z+w+1>y+w+1$
這表示分母的每個因子都比對應的較小值更大，因此分母的增長速度會比單純的平方更快，接近四次方級別 $O(n^4)$。

因此我們得知大括號內恆為正，整個表達式為正。
情況2：如果 $j$ 和 $n-j$ 都是奇數，處理方式類似，也能證明 $D > 0$。

透過這兩種情況，證明了對於任何 $1 ≤ j < ⌊\frac{n}{2}⌋$，選擇$j = ⌊\frac{n}{2}⌋$ 總是比選擇其他 $j$ 更優。

因此，在每個遞迴階段選擇 `half-half rule` 是最好策略，這就是為什麼 TDM 在 average case 下是最好的 mergesort。

:::info
雖然 QM 以及 list sort 都不是使用 half-half rule，但我認為從這個 theorem 可以理解到為什麼每次合併的兩個元素的長度要盡量接近。
而實際上 QM 以及 list sort 的合併方式也確實遵循這個規則。
:::

### Theorem 6
QM 的 variance 是 asymptotically optimal。
####

## 個人小記
::: danger
list_sort 為什麼又更好？
論文提及的 queue merge 有以下性質
在固定的 $i$ 時，最多有一個 $a_{i,j}$ 不是 2 的冪
> 還真的分析錯誤 我需要再看一下原始碼
以下整段話都是錯的！別參考 我只是留著紀錄

但是 list_sort 不是每次都會合併 他會判斷現在元素的數量是不是 $3 * 2^k$ 是的話才會合併 所以代表他只有在完成所有合併前的最後一步 才有可能出現 不是 2 的冪的合併行為

所以代表他不是
在固定的 $i$ 時，最多有一個 $a_{i,j}$ 不是 2 的冪
他是
在最後一步時，最多有一個 $a_{i,j}$ 不是 2 的冪
前面的迭代都不會出現 $a_{i,j}$ 不是 2 的冪的情況

:::
以上應該改成：在最後合併階段，為不會再有新的節點加入 pending 之後，才可能最多會有一個不是 2 的冪的元素長度出現。
所以其實 list sort 的這個行為會跟 queue mergesort 一樣，主要的差別應該在於發生合併的條件以及 list sort 會是 stable sort 但是 queue mergesort 不會。