論文

問題：
（林本然）

1. 數量跟比較次數有關係，但為何還要分最差、最糟、平均來討論呢？差異是？
2. 比較次數 C(n) 中的 +1 從何而來？

(林志芸)

(邱繼寬)
4. 如何證明 queue-merge sort 相對於其他合併排序，在最糟情況下的比較次數是最少的？其他為何會比較多？
(All)
5. 對合併排序而言，何謂最佳、最差？
6. 為什麼 bottom up 比較友善？

list_sort 流程：

何時合併？

如何合併？

演示利用 list_sort 將鏈結陣列 [1, 8, 9, 6, 4] 排序成 [1, 4, 6, 8, 9] 的過程

補充 Attributes

先觀察 queue-merge sort 的合併流程
queue-merge sort
[1, 8, 9, 6, 4] -> [1, 4, 6, 8, 9]

把 「放回 tail」 想像成放進一個叫 tail 的新鏈結串列

1. $[1,8,9,6,4]$ ->
   $[9,6,4]$ +
   $[(1,8){]}_{tail}$

2. $[9,6,4]$ ->
   $[4]$ +
   $[(1,8),(6,9){]}_{tail}$

3. $[(1,8),(6,9),4]$ ->
   $[4]$ +
   $[(1,6,8,9){]}_{tail}$

4. $[1,4,6,8,9]$

queue-merge sort 是藉由 queue 裡面的順序來決定要合的節點（頭兩個），那 list_sort 呢？

決定多少節點要被放入 pedding

for (bits = count; bits & 1; bits >>= 1)
    tail = &(*tail)->prev;

Bottom-up Mergesort: A Detailed Analysis

林本然

Introduction

Merge Sort 總共有三種變體：Top-down, Bottom-up, Queue Merge Sort（底下已提及），在 Introduction 提及影響 Merge Sort 最關鍵的是 merge 階段的比較次數

$C(N)$ ，因為比較次數對運行時間影響比較大。這裡用

$C_{b,td}(N)$,

$C_{a,td}(N)$,

$C_{w,td}(N)$ 來表示 top-down 版本分別在 best, average, worst-case 的比較情況，可以這樣進行處理，其中，週期函數

$A(x)$ 被定義如下，

$\{x\}$ 代表的是

$x$ 的小數部份，即

$\{x\}=x-\lfloor x\rfloor$ 。（參見 Fractional part）

$$C_{w,td}(N)=N\log N+NA(\log N)+1$$

$$A(x)=1-\{x\}-2^{1-\{x\}}$$

使用 Geogebra 繪製

$A(x)$ 如下：

圖片網址遺失。
By Urbaner

可以看到週期函數是以週期為 1 而波動的，而要關注小數部份的原因是 merge sort 在進行分割的層數是

$\log N$ ，但

$\log N$ 並不會每次都取得整數，在

$N$ 不是 2 的冪的情況：

$$\log N=k+\{\log N\}$$

$k$ 是整數部份，

$\{\log N\}$ 是小數部份，因此在 2 的冪之間，小數會呈現週期性的波動，這也是

$C_{w,td}(N)$ 為什麼有

$NA(\log N)$ 這一項的原因，因為要將小數部份的比較次數也算進去。

舉例來說：10 和 12 就因為不是 2 的次方，所以分出來的子串列長度不平均，其中又以 12 波動最大，子串列長度在 2 和 1 之間來回跳動，因此這些子串列的 merge 比較次數也在 1 和 0 之間波動。因此當

$\{\log N\}\approx 0$ ，代表

$N\approx 2^k$ ，反之若

$\{\log N\}\approx 1$，代表

$N$ 離

$2^k$ 很遠。

資料大小 $N$	${\log }_{2}N$	小數部分 $\{{\log }_{2}N\}$	Partition 左右比例	比較次數波動
8	3	0	完全平衡	最小
10	3.3219	0.3219	不均勻	較小 (5+5 $\to$ 3+2+3+2 $\to$ 2+1+2+2+1+2+1)
12	3.5849	0.5849	完全不均勻	較大 (6+6 $\to$ 3+3+3+3 $\to$ 2+1+2+1+2+1+2+1)
16	4	0	完全平衡	最小

回到原本的

$C_{w,td}(N)$ 公式，可以知道

$N\log N$ 是每一層的元素數量（都是

$N$）乘上總層數，再加上小數部份導致的額外比較次數

$NA(\log N)$ ，最後

$+1$ 則是向上取整，避免數據量過小的時候

$C_{w,td}(N)$ 變為 0。

Bottom-Up Mergesort

以下簡稱 BM。

BM 以迭代取代遞迴，並且等全部的子串列被分割之後，由小子串列合併至大的子串列，並且以 p, q 表示目前兩個子串列的頭的索引值。其中 length := 1 表示從長度為 1 的子串列開始合併，過程中判斷若 q + length >= N 且 q < N 表示剩下元素不足以自己合併出一個 length * 2 長度的子串列，會拿上一個已經合併完成的子串列來合併。

• 舉例：合併 [1] [4] [9] [3] [2]
• [1, 4] [3, 9] [2]
• [1, 3, 4, 9] [2]
• [1, 3, 4, 9, 2]

Algorithm MergeSort(a[1 .. N])
begin
    length := 1;
    while length < N do
    begin
        p := 0;
        q := length;
        while q + length <= N do
        begin
            Merge(a[p + 1 .. p + length], a[q + 1 .. q + length]);
            p := q + length;
            q := p + length;
        end;
        if q < N then
            Merge(a[p + 1 .. p + length], a[q + 1 .. N]);
        length := 2 * length;
    end
end;

而遞迴版則是每次皆進行分割，但是依 2 的冪 來分割。每次分割其中一半都是取前面的

$2^{\lceil \lg N\rceil -1}$ 個元素，另一半就是剩下元素。

要排序的元素數量

$N$ 的二進位可以被表示為以下：

$$N=(b_k{b}_{k-1}...b_1{b}_0{)}_2$$
合併過程中，最底部會有

$\lfloor N/2\rfloor$ 次的 (1,1) 合併，(1,1) 代表兩個長度為 1 的子串列合併。下一層則會有

$\lfloor N/2\rfloor$ 次的 (2,2) 合併，且若

$N\mathrm{mod}4>2$ 又會有不完整合併 (2, N%2)，因為要剩下超過 2 個元素才會又構成一次不完整合併。根據這過程可歸納出在 level j 的時候：

• 完整合併次數：
  $\lfloor N/2^{j+1}\rfloor$ of type (2^j, 2^j)
• 不完整合併次數：1 次 type of (2, N % 2^j)
• 不完整合併的數學條件為：
  
  $$N\mathrm{mod}{2}^{j+1}>2^j$$
• 可以用二進位表示成：
  
  $$b_j\cdot (b_{j-1}...b_1{b}_0{)}_2>0$$
  若且唯若第 j 位為 1 而剩下的位元不為 0 。

Algorithm MergeSort(a[1 .. N])
begin
    if N >= 2 then
    begin
        MergeSort(a[1 .. 2⌊log_2 N⌋ - 1]);
        MergeSort(a[2⌊log_2 N⌋ - 1 + 1 .. N]);
        Merge(a[1 .. 2⌊log_2 N⌋ - 1], a[2⌊log_2 N⌋ - 1 + 1 .. N]);
    end;
end;

這樣可以控制每一層合併時只有最多一次的不完整合併，使得 bottom-up 在不同 case 的情況下比較次數會更穩定，因為波動的只有那一次不完整合併。

根據論文所述，總共合併次數為

$N-1$（因為總共

$N$ 個子串列最少需要

$N-1$ 次合併），其中包含

$\lfloor N/2\rfloor +\lfloor N/2^2\rfloor +...+\lfloor N/2^k\rfloor$ 次完整合併，和

$b_0+b_1+...b_k-1$ 次不完整合併。因為在遞迴版 BM ，每一個分割出來的子串列長度全部都是 2 的冪，所以可以照二進位表示得知分割完有

$b_0+b_1+...b_k$ 個子串列，要合併這些子串列，最少會需要

$(b_0+b_1+...b_k)-1$ 次合併。

舉例：

$N=13=(1101{)}_2$

• 長度 13 總共有
  $\lfloor 13/2\rfloor +\lfloor 13/2^2\rfloor +\lfloor 13/2^3\rfloor +\lfloor 13/2^4\rfloor =6+3+1+0=10$ 次完整合併。
• 長度 13 的子串列會被分為 [8, 4, 1]，因此會有 (4,1) 和 (8,5) 共 2 次不完整合併
• $b_3+b_2+b_1+b_0-1=1+1+0+1-1=2$
• 所以總合併次數是
  $10+2=12$，也剛好
  $12=N-1$ 。

Axiom

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

Best Case

Best Case 代表每一次子串列的合併都會是最棒的，也就是子串列的值完全不交錯，短的串列一直被比較並 merge，總共就只會比較

$min\{n,m\}$ 次。

跟林志芸的 QM 比較一下如果以 top-down 的觀點來看要怎麼解釋。
balance-power-of-2 v.s. power-of-2

Queue-Mergesort

邱繼寬

此論文介紹了一種合併排序的變形：Queue-Mergesort 一種最壞情況下最優的 mergesort 變體
Queue-Mergesort 是專門用於 linked-list 的排序演算法
其原理是利用 q_get 取出 linked-list 的頭兩個節點
利用 Merge 排序後，利用 q_put 放回 linked-list 的尾端。取節點的方是 FIFO ，跟 queue 一樣。

The two lists to be merged, are the two smallest lists one the queue.

while (Q.size != 1) do
    Q.put(Merge(Q.get, Q.get))

其運作模式如下 (a)~(f)：

以 list.h 風格實作 q_put 和 q_get

什麼是最壞情況呢？

最壞就是比較次數最多
若兩個 linked-list A 和 B 的節點數量分別為

$n_1$ 和

$n_2$
最差的情況為比較次數即為 (

$n_1+n_2$)

跟 top down 的差別？

文中提到 Queue-Mergesort 跟 top-down mergesort 有幾分相像

like top-down mergesort but unlike bottom-up mergesort

差別在如何選擇要進行 Merge 的節點（或是子串列）
以 top-down mergesort 為例，其合併節點的順序為遞迴呼叫在堆疊中的順序。

而 Queue-Mergesort 則是用 queue 來決定哪兩個節點（或是子串列）要被合併，就像小孩在排對使用溜滑梯一樣，排序完就要重新排隊。

什麼是最優呢？

論文提及了一種分析工具：merge-tree
merge-tree 描述的是在排序過程中的狀態，下方圖中，方格代表還未被排序的節點，圓圈代表合併後的子串列，數字代表子串列的長度（節點數）
此論文使用函數

$w(i)$ 編號 i 的節點在 merge-tree 中的對應的數字

而最差情況下的比較次數即為

$w(i)-1$
因此節點數量為

$n$ 的 linked-list 在最糟情況下的比較次數即為

$\sum _{i=1}^n[w(i)-1]$
可表示成以下關係：

$\sum _{i=1}^n[w(i)-1]=[\sum _{i=1}^{n}w(i)]-(n-1)$

以上圖為例，在排序 11 個節點的情況下：

• (a) queue-merge sort 需要 39 次比較
• (b) Top-down 需要 39 次比較
• © bottom-up 需要 40 次比較

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$$
2. Bottom-up mergesort
   power-of-2 rule
   
   $$\tau (n)=2^{\lfloor {\log }_2(n/2)\rfloor }$$
3. 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.

但是 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,n\ge 2$$
其中：

• $g_n$ 表示合併成本
• $\rho =min\{2^{\lfloor {\log }_2(2n/3)\rfloor },n-2^{\lfloor {\log }_2(2n/3)\rfloor }\}$ ，即兩個子問題中較小的那個
• $\lambda =n-\rho$，即較大的子問題
• $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}\le a_{i,i+1}\le ...\le 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 時：

此時

$a_{1,1}$ 到

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

此時變成

$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}$，這是因為新的佇列的最後一個鏈結串列即為原本的前面兩個鏈結串列的合併結果。

註：紅色的箭頭不是指標！只是用來表達

$a_{2,j}=a_{1,j+1}$

透過歸納法，可以證明

$a_{i,j}$ 滿足以下性質：

1. 存在整數
   $k$，使得
   $2^k\le a_{i,j}\le 2^{k+1}，j=i,...,n$
2. $1/2\le a_{i,j}/a_{i,j+1}\le 1，j=i,...,n-1$
   • 每個佇列裡面的元素（鏈結串列）的下一個元素的大小，一定不是跟自己一樣大，就是自己的兩倍大以下。
   • 由
     $a_{i,j}\le a_{i,j+1}\le 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 的冪

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$。

QM 總是選擇長度最小的兩個鏈結串列合併，這自然會形成一種平衡，使得最終剩下的兩個鏈結串列的大小盡可能接近。
最終，當佇列中只剩下兩個鏈結串列時，

$\rho$ 和

$\lambda$，而這也正是使用

$\rho =2^{\lfloor {\log }_2(2n/3)\rfloor }$ 規則進行 top-down 分割得到的結果。

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

我自己的理解是：
QM 用一種類似 top-down 的想法（？）來實作 bottom-up，他保留了 bottom-up 的好處與特性，比如說實作上只需簡單的佇列操作和迴圈，以及單純合併對 cache 更加友善等等，但他同時在效能上擁有 worst case optimal 以及 asymptotically optimal，不需要透過像 TDM 的切割步驟，QM 就擁有了類似於 TDM 的平衡特性。

3/22 讀書會討論的時候，在這個部分聯想到林本然負責研讀的論文：
〈 Bottom-up Mergesort: A Detailed Analysis 〉
當中有提到遞迴版本的 bottom-up，我們認為也是用 top-down 想法詮釋 bottom-up 的實例之一。

LEMMA 2

描述了 heap recurrence 的解：

$$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}$$
其中：

$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\le j\le \frac{n}{2}$，那麼它在最壞情況下都是最優的。

$r\le j\le \frac{n}{2}$ 是一個條件：

• $r$ 在 QM 中是指
  $2^{\lfloor {\log }_2(2n/3)\rfloor }$，即不超過
  $\frac{2n}{3}$ 的最大 2 的冪
• $\frac{n}{2}$ 是傳統上 TDM 所採用的切割點

換句話說，只要切割點不要選得太小（至少要

$\ge r$），也不要超過中點（

$\le \frac{n}{2}$），那麼這個 mergesort 在最壞情況下就會是最優的。

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

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

$O(n²)$，遠大於 QM 和 TDM。

論文這邊很輕巧的帶過週期性的部分，我也不是很理解，可以去看林本然那篇！
第四章證明其 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)\},n\ge 2,1\le j\le n-1$

其中

$u(x,y)$ 是合併兩個已排序元素的平均比較次數，定義為：

$$u(x,y)=x+y-\frac{x}{y+1}-\frac{y}{x+1}$$
我們需要證明：對於任何

$n\ge 2$，

$U(n)$ 的最小值會在

$j=\lfloor \frac{n}{2}\rfloor$ 出現，即為切一半。

基礎情況：
當

$n=2$ 或

$n=3$ 時，結論顯然成立：

• 對於
  $n=2$，只有
  $j=1$ 這一種選擇
• 對於
  $n=3$，
  $j=1$，平均切割是選擇
  $j=1$（因為
  $\lfloor \frac{3}{2}\rfloor =1$ ）

歸納假設:
假設對於所有小於

$n$ 的正整數

$k$ ，最好的分割點是

$j=\lfloor \frac{k}{2}\rfloor$。

需要證明對於

$n\ge 4$ ，當

$1\le j<\lfloor \frac{n}{2}\rfloor$ 時：

$$D=U(j)+U(n-j)+u(j,n-j)-U(\lfloor \frac{n}{2}\rfloor )-U(\lceil \frac{n}{2}\rceil )-u(\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil )>0$$

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

$$U(j)=U(\lfloor \frac{j}{2}\rfloor )+U(\lceil \frac{j}{2}\rceil )+u(\lfloor \frac{j}{2}\rfloor ,\lceil \frac{j}{2}\rceil )$$

$$U(n-j)=U(\lfloor \frac{n-j}{2}\rfloor )+U(\lceil \frac{n-j}{2}\rceil )+u(\lfloor \frac{n-j}{2}\rfloor ,\lceil \frac{n-j}{2}\rceil )$$

2. 考慮兩種情況：
   情況1：如果

   $j$ 或
   $n-j$ 為偶數
   則：
   
   $$\lfloor \frac{j}{2}\rfloor +\lfloor \frac{n-j}{2}\rfloor =\lfloor n/2\rfloor$$
   
   $$\lceil \frac{j}{2}\rceil +\lceil \frac{n-j}{2}\rceil =\lceil n/2\rceil$$
   將展開代入D中，可以得到：
   
   $$D=u(\lfloor \frac{j}{2}\rfloor ,\lceil \frac{j}{2}\rceil )+u(\lfloor \frac{n-j}{2}\rfloor ,\lceil \frac{n-j}{2}\rceil )-u(\lfloor \frac{j}{2}\rfloor ,\lfloor \frac{n-j}{2}\rfloor )-u(\lceil \frac{j}{2}\rceil ,\lceil \frac{n-j}{2}\rceil )+u(j,n-j)-u(\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil )$$
   經過代數變換，對於任意
   $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\le j<\lfloor \frac{n}{2}\rfloor$，推知
   $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\le j<\lfloor \frac{n}{2}\rfloor$，選擇

$j=\lfloor \frac{n}{2}\rfloor$ 總是比選擇其他

$j$ 更優。

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

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

Theorem 6：QM 的變異數是 asymptotically optimal。

個人小記

list_sort 為什麼又更好？
論文提及的 queue merge 有以下性質
在固定的

$i$ 時，最多有一個

$a_{i,j}$ 不是 2 的冪

還真的分析錯誤 我需要再看一下原始碼
以下整段話都是錯的！別參考 我只是留著紀錄

但是 list_sort 不是每次都會合併 他會判斷現在元素的數量是不是

$3\ast 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 不會。

---

例子

11

8->2->1->1
8->2->2->1
8->2->3
8->5
13

3/17

如何證明是 stable sort ?

2(2, 8) 1 (1) -> 一次
2(2, 8) 1(9) -> 兩次

都是六個

的最糟情況 -> 比較次數最多 -> 兩個數列減少的速度一樣

[1, 3, 5] + [2, 4, 6]

個數相同的最好情況 -> 比較次數最少 -> 一個數列提早結束

[1, 2, 3] + [4, 5, 6]

問題

是否為二的冪所帶了的影響為何？

猜測

1. 合併的兩個鏈結串列若長度差距太大會怎樣？

---

畫圖：

[1, 1] [1, 1] [1, 1] 1
2 2 2 1
4 3
7

[1, 1] [1, 1] [1, 1] 1

queue merge

1 1 1 1 1 2
1 1 1 2 2
1 2 2 2
2 2 3
3 4
7