2024q1 Homework2 (quiz1+2)

contributed by < randyuncle >

TODO:

• 預計先做第一週測驗作業二，了解 Tim sort 和 lib/list_sort 的差別，以銜接 M03 中對於 Tim sort 引入 lab0-c 的檢查要求

quiz1 – 測驗一

前言

在此題中的快速排序法參考的是 Optimized QuickSort — C Implementation (Non-Recursive)。在這篇文章中，作者依舊使用頭部節點（也就是鍊結串列的第一個節點）做為每一輪比較的 pivot。但和常見的快速排序法不同的是，作者使用固定大小的堆疊陣列，去取代遞迴呼叫所使用的記憶體堆疊。

除此之外，此程式的交換在每輪遍歷時，指標 L 和 R 遇到比 pivot 大和比 pivot 小的值的場合，就會觸發，直到 L >= R 為止，且每輪只會觸發一次，而非像常見的快速排序法一樣，在每輪的排序途中做複數次交換。

此題鏈結串列的運作

鏈結串列結構體

在此題中，自定義了一個鏈結串列結構體：

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

對應的結構圖如下：

在 node_t 結構體中，它有一個指標 next、一個整數型態變數 value、以及兩個在測驗題的參考程式中沒看到有特別著墨的 left 和 right 指標。由此可推測此為一個單向的鏈結串列。

接下來，將針對維護此鏈結串列的操作函式做說明。

list_add

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;
    *list = node_t;
}

list_add 函式主要功能是將新的節點連進鏈結串列中。由於結構體 node_t 中的 next 變數是個指標，因此若要賦予 node_t->next 內容的話，需要引入的參數 list 需為指標的指標。

我們假設

• 鏈接串列參數 node_t **list 指向的結構體的整數型態變數 value 為 A
• 結構體參數 node_t *node_t 的整數型態變數 value 為 B

此函式運作完後的 node_t *list 可得到如下圖的結果：

可以發現到欲連入鏈接串列的節點（node_t *node_t），會被接在原本的鏈接串列頭部節點（node_t **list）的前面，成為新的頭部節點。

list_tail

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &((*left)->next); //AAAA
    return *left;
}

list_tail 函式的功能是回傳指定參數鏈接串列的最後一個節點，以 while 迴圈寫成。

運作的方式可參考以下的圖：

首先，引入的鏈接串列會是下列的形式

Error: viz.js output empty graph

之後，在經過第一次迭代操作後，可以得到以下的狀態

Error: viz.js output empty graph

重複以上的操作，直到到達鏈接串列的最後一個節點，也就是 (*left)->next 和 (*left) 任一項不存在的場合（不過通常都是 (*left)->next 不存在就會跳出迴圈）。

---

quiz1 – 測驗二

解釋 Tim sort 程式碼運作原理

Tim Sort 的運作分為兩個部分：分割和合併。與 lib/list_sort 中實現的 merge sort 相似之處在於，它們都優化了對 cache 的使用，即在分割序列時，就已經啟動了合併操作，這樣可以在非連續記憶體序列還在 L1 cache 中時就開始進行合併。除此之外，它們在合併的規則都有參考 2 的冪，以有較佳的比較次數。

在測驗二中的程式，使用了 Linux 核心的 list.h API，以及於 lib/list_sort 中所實現的合併策略。比較需要注意的是 lib/list_sort 合併策略的引入，使得此程式不需要按照作者原來的構想 – 額外令一個空間去存取合併後的結果，使其之記憶體開銷降至最低。

接下來，以下將針對部分的程式碼操作做說明。

tim_sort

執行 Tim sort 的主要函式。

首先，Tim sort 在排序的開頭，會先走訪過一遍鏈接串列，也就是以下 do-while 迴圈在做的操作：

do {
    /* Find next run */
    struct pair result = find_run(priv, list, cmp);
    result.head->prev = tp;
    tp = result.head;
    list = result.next;
    stk_size++;
    tp = merge_collapse(priv, cmp, tp);
} while (list);

在走訪鏈接串列的過程，Tim sort 會以 find_run 函式，將鍊接串列分割成一條一條各自已排序成由小到大的子串列，並將每一輪的分割子串列之頭尾節點指標回傳給變數 result，以將其接入堆疊串列 tp 中。

在堆疊串列 tp 成功接入新的子串列、更新了目前堆疊的高度後，會交由 merge_collapse 函式，決定是否要將堆疊中的部分串列合併。關於 merge_collapse 函式的運作後續會說明。

以上操作完成後，接下來會使用 merge_force_collapse() 函式，將剩餘的 run 串列強制合併。

/* End of input; merge together all the runs. */
tp = merge_force_collapse(priv, cmp, tp);

最後，tim_sort 函式會先確保所有的子串列都變成雙向鏈接串列，之後，再將剩下的子串列合併在一起。其中，這裡合併策略使用了 lib/list_sort 的實作方法完成。

/* The final merge; rebuild prev links */
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
    stk0 = stk0->prev, stk1 = stk1->prev;
if (stk_size <= FFFF) {
    build_prev_link(head, head, stk0);
    return;
}
merge_final(priv, cmp, head, stk1, stk0);

如果我們對比 lib/list_sort 的 list_sort 函式的結尾處，會發現上面列出的程式碼的實作是非常相似於 list_sort 函式得處理方式。

find_run

Tim sort 中，尋找所有已排序的子序列，並在運作途中，會將 descending order 的子序列直接轉成 ascending order 的函式。回傳的資料型態為一個包含子序列頭尾節點的結構體。

/* Return data type of function `find_run` */
struct pair {
    struct list_head *head, *next;
};

在分辨是否為 descending order 子序列的方式，由以下的 if 判斷條件所掌握：

cmp(priv, list, next) > 0

這條函式的含意，主要是判斷是當前輸入的節點值 ( value ) 和它下一個的節點值的大小差別。如果 list->value > next->value，代表此子序列有可能是 descending order；反之，則為 ascending order，或兩兩相同。其中，這裡的 cmp 函式和 lib/list_sort 中代表的意思是一模一樣的。

如果經過此比較函式的比較後，發現結果為 list->value > next->value 的話，當前的子序列為 descending order 的結構，需要將其反轉，也就是下列的程式碼所做的操作：

do {
    len++;
    list->next = prev;
    prev = list;
    list = next;
    next = list->next;
    head = list;
} while (next && cmp(priv, list, next) > 0);

以 do-while 迴圈，將節點一個一個反接成 head 節點的前一個節點

並將 head 節點更新為反接的節點

另一方面，如果此子序列是 ascending order 的話，則做 do-while 迴圈的掃描，直到下一個節點 ( next 指標 ) 比當前節點 ( list 指標 ) 的值 ( value ) 大為止。

do {
    len++;
    list = next;
    next = list->next;
} while (next && cmp(priv, list, next) <= 0);

在函式的最後，則是一個將該 run 的頭部節點之 prev 指標令為 NULL，暫時斷掉和原鏈接串列的連結。

head->prev = NULL;
head->next->prev = (struct list_head *) len;

比較需要注意的是，在頭部節點的下一個節點的 prev 指標中，是令其指向為 len 變數。而這裡的 len 變數，在函式開頭就有做以下的型態定義和初始化：

size_t len = 1;

所以，在每輪 find_run 函式運作完，其所分割出來的 run 串列之 head->next->prev 指標，都會指向一個為 size_t 資料型態的變數 len，並且變數 len 會被強轉型為 struct list_head * 指標的資料型態。

run_size

一個用來計算目前 run 串列的大小（也就是節點數量）。

static inline size_t run_size(struct list_head *head)
{
    if (!head)
        return 0;
    if (!head->next)
        return 1;
    return (size_t) (head->next->prev);
}

前兩個 if 條件判斷是用來直接排除沒有節點或只有一個節點的情況。若輸入的引數 head 指標有多於一個節點的話，則會回傳存在 head->next->prev 的 size_t len 數值，表示此 run 串列的長度大小。

merge_collapse

決定是否要在 Tim sort run 操作中進行堆疊串列合併的函式，確保每個 run 的長度差距不至於差到太多。決定合併的判斷依據是在堆疊 ( tp 指標 ) 中的 run 串列的大小比較，以及堆疊中的 run 串列的數量。

在此程式中，主要對於 run 串列的合併條件為以下：

該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：

1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。

從以上的幾個條件，也可以知道，此程式實作的 Tim sort 的 minimum run size 的選擇並非是一個固定的值，而是一個 run 串列之間比較權衡的結果，平衡各個 run 串列的長度差距。

在程式中的實作為以下：

• 堆疊中的 run 串列數量多於 3，且堆疊 tp->prev->prev 的 run 串列大小不大於 tp->prev 和 tp 指標指向的串列的總和；又或者，堆疊中的 run 串列數量多於 4，且堆疊 tp->prev->prev->prev 的 run 大小不大於 tp->prev->prev 和 tp->prev 指標指向的串列的總和。

  ​​​​if ((n >= 3 &&
  ​​​​     run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
  ​​​​    (n >= 4 && run_size(tp->prev->prev->prev) <=
  ​​​​                   run_size(tp->prev->prev) + run_size(tp->prev)))
  

  • 若 tp->prev->prev run 串列大小小於 tp run 串列，以 tp->prev run 串列為基準引入 merge_at 函式執行合併。
    ​​​​​​​​if (run_size(tp->prev->prev) < run_size(tp)) {
    ​​​​​​​​    tp->prev = merge_at(priv, cmp, tp->prev);
    ​​​​​​​​}
    

  • 若非以上條件，則以 tp run 串列為基準引入 merge_at 函式執行合併。
    ​​​​​​​​tp = merge_at(priv, cmp, tp);
    

• tp->prev 指標指向的 run 串列大小不大於 tp 指標指向的 run 串列。

  ​​​​else if (run_size(tp->prev) <= run_size(tp)) {
  ​​​​    tp = merge_at(priv, cmp, tp);
  ​​​​}
  

merge_force_collapse

在 tim_sort 函式走訪完整個鏈接串列後，將整個堆疊中的 run 串列強制合併的函式。主要看當前堆疊的前三個 run 串列之間的狀態比較，來決定合併的方式。

判定合併方式的條件，即為前述 merge_collapse() 函式中的第一個項目符號符合後所進的 if-else 條件式。

merge_at

將輸入引數 at 指標以及它的前一個指標 at->prev執行合併操作的函式。

執行合併前，會先將合併後的串列大小做加總，並存成 size_t 資料型態的變數

size_t len = run_size(at) + run_size(at->prev);

執行合併的方式，則是使用 lib/list_sort 的合併策略，將 at 指標以及他的前一個指標 at->prev 指標合併成一個新的 run 串列。

struct list_head *list = merge(priv, cmp, at->prev, at);

在合併完成後，此函式會進行與 find_run() 函式結尾相同的操作，亦即，將合併後的 list 指標的下一個節點指向的前一個指標 (list->next->prev) 更新為新的 size_t 資料型態的變數。

list->next->prev = (struct list_head *) len;

將 Timsort 引入進 lab0-c

詳見：整合 Tim sort 進 queue.c

提出改進方案並實作之

Tim sort 相比於傳統 merge sort，多了幾個為了 cache-friendly、有助於減少比較次數、且理論可在合併時做到最佳平衡的技巧：

• Defining minimum run size while finding runs.
• Introduces galloping mode during merging.

而這兩個想法在原程式是沒有落實的，因此以下我想將以上的兩個想法落實進原程式中，並比較若實現這兩個想法進去後的比較次數及效能差異。

Minimum run size

從前一節的描述以及實作中，可以看到 Tim sort 在做合併之前，都會先走訪過一次整個資料結構中的所有元素，以找到每一節的 ascending ( 或 descending ) order。為了能夠保證每個 run 都有一個基礎大小，使其可以做到均勻的合併，Tim sort 的作者設定了一個被稱為 MAX_MINRUN 的變數，規定每條 run 限定的最小長度大小。作者也同時在原實作中寫下了配套的求取機制：

take the first log2(MAX_MINRUN) bits of N, and add 1 if any of the remaining bits are set. In fact, that rule covers every case in this section, including small N and exact powers of 2; merge_compute_minrun() is a deceptively simple function.

簡單來說，每條 run 的最短長度，就是原本的 MAX_MINRUN 變數取 log₂ 的結果。

如果在 find_run 的過程中，有一條 run 的長度比最短的 run 長度要小的話，則會需要填補缺少節點進去該 run 中。作者在填補後，會以 binary insertion sort 的方式做重新排序，使其變成 ascending ( 或 descending ) order。雖然在程式中，可以知道每條 run 當下的長度，但是在鏈接串列中，並不太好使用二分搜尋法的方式插入節點，因為就算得到中點的資訊，仍需要使用迴圈等方式，將指標定位到該節點上。

在我查看 cpython 中的 listsort.txt 的內容時，看到了裡面做 galloping mode 時的 "galloping" 運作原理，於是嘗試使用類似 galloping 的方式，在 commit 19e34a5 中是以兩兩節點一同讀取的方式，取代原本使用二分搜尋法，去找到節點應插入的位置。

• linear searching during insertion sort

commit 19e34a5
2024/4/23 在想能不能把 findrun() 用指標的指標重新撰寫，不然現在的做法需要先將串列的 prev 指標重新建成以避免無限 loop bug 出現。

commit 19e34a5 是我目前的實作結果。關於其中的 minimum run size 的求取已在 commit message 中做簡易的描述。

在 listsort.txt 中，對 "galloping" 作法有以下的說明：

In galloping mode, we first look for A[0] in B. We do this via "galloping", comparing A[0] in turn to B[0], B[1], B[3], B[7], …, B[2j - 1], …, until finding the k such that B[2(k-1) - 1] < A[0] <= B[2**k - 1]. This takes at most roughly lg(B) comparisons, and, unlike a straight binary search, favors finding the right spot early in B (more on that later).

在原描述的定義中，"galloping" 主要是以 0, 1, 3, 7, …, 2^k+1 的節點定位去找到節點大略會插入的範圍。不過，由於每個 run 的最低限定大小並不大（根據程式的設定，每條 run 的長度都不大於 32），因此我使用兩個指標 curr 以及 prev 去存取兩兩相鄰的節點，並以最大兩個節點的距離（curr->next->next）做走訪，搜尋合適節點插入點，從而降低單一節點距離（curr->next）走訪所帶來的比較次數差距。

TODO:

• 將新舊版本的程式分開
• 尋找自動測試的方法，可能需有以下的功能：
  1. 能多重複運作整個程式，紀錄每次的結果
  2. 根據結果生出圖表

• binary searching during insertion sort

不過，另一方面，我還是想要測試如果真使用二分搜尋法尋找插入節點的話，它所需要的比較次數與運行時間的差距究竟為何。

在本程式中的 binary search，首先依靠變數 len 得知本次 run 的長度，接下來依序迭代尋找每一輪搜尋的中點。只是相比於上面的線性走訪來說，這方法在 linked-list 可能會需要更多的指標操作（例如說以 while 迴圈定位 run 的中點），以找到合適的目的地。為了知道它們之間的比較次數和運行時間差距，所以我寫了 binary insertion sort for minimum run size 做實驗

commit 78aa968

commit 78aa968 是我將原本實作給 min run strategy 的 linear insertion sort 改成 binary insertion sort。中點的求尋主要由以下的程式碼所取得：

int middle = (x & y) + ((x ^ y) >> 1);

• 測試結果

本次的測試，是為了測試使用 linear insertion sort 或 binary insertion sort min run strategy 的 Tim sort，和原本的 Tim sort 程式之間的比較次數和運行時間的差距。測試程式的製作可見這連結，且本次的函式測試皆在 lab0-c 的環境中運作。

測試方式：

1. 從直譯器 qtest.c 執行 stest 命令，啟動測試程式 sort_test.c。
2. 測試的節點數範圍為 4 ~ 8192，且每個節點數都會重複生成資料及排序 15 次（原本是想效訪 dudect 的測試，每個節點數都跑 150 次，但這樣跑一個星期也跑不完）。

測試可分為三個項目：

1. Comparisons：每次排序所需要的比較次數。
2. K-value：參考 kdnvt 的共筆的方法。在此篇筆記中，作者參閱了 Bottom-up Mergesort: A Detailed Analysis，藉由裡面對於比較次數和排序序列的元素數量的關係，了解其中 K 值的意義，並以此關係寫出計算 average k value 的程式碼。不過，在本次的測試中，我沒有要計算 average k value，因此只將 k value 的計算引入進測試程式之中。本次加入 k value 運算有一個好處 – 能夠精確地觀察到每個節點數所對應的比較次數週期，以及比較的穩定性。
3. Duration time：計算每次排序所需要的時間。本次測試中，測量時間的工具用的是 dudect 資料夾中的 cpucycle.h 標頭檔，分別取得排序開始前和結束後的 cpu cycle，以得到排序過程所經歷的 cpu cycles。

測試完成後的 gnuplot 結果如下：

完全隨機的資料

升冪資料，隨機 3 個資料換成隨機資料

升冪資料，最後 10 個資料換成隨機資料

升冪資料，隨機 1% 個資料換成隨機資料

有多個重複的資料

Worst case scenario for merge sort

Discussion

從以上的 gnuplot 可以發現，使用 binary insertion sort 作為 Tim sort 中的 minimum run insertion strategy，可以使得 Tim sort 的比較次數，以及其對應的 k-value，隨著序列中節點數量的增加，皆以直線穩定的增長，尤以隨機資料和 worst case scenario 的結果可以很明顯的看到此現象。

如果我們只看 k-value 分佈圖的結果的話，藉由每個節點數中不同的 Tim sort 實作的表現，可以得知 linear insertion sort 所造成的 k-value 都是最低的，變相的表示其之比較次數在這三個實作中，是最高的；而另一方面，binary insertion sort 則會控制整體的比較次數，使其在 k-value 的分佈處於原本的 Tim sort 和實作於 minimum run strategy 的 linear insertion sort 之間。

不過，若要執行 minimum run strategy，會導致在 find_run() 階段時，因為要以 insertion sort 的方式插入節點，會產生額外的比較和指標操作，所以原本的 Tim sort 的比較次數（包含 k-value 分佈的觀察）會是三個實作中最容易出現最少比較次數，且在時間分佈的中的 lower bound 也會是三個實作中最低的（除了在 worst case 中，timsort /w binary minrun 在某些節點數會出現最小的排序時間）。因此，如果要降低比較次數，要在後續將 gallopping mode 實作出來，才能知道原先 Tim sort 的構想，在鏈結串列的實作中，是否會比其他的排序演算法（例如說 lib/list_sort）要好。

The galloping mode

在 listsort.txt 中，galloping mode 可以分成兩個部分：

• exponential searching the boundaries
• binary searching within the identified boundaries。

我在 Minimum run size 小節中已經提過 exponential searching。簡單來說，就是以 2 的冪次做為間距的搜尋。在原本的 Tim sort 應用中，作者將此動作命名為 "galloping"，其作用是在排序合併時，於另一條 run B 中尋找可以插入輸入最小 run 中節點 A[0] 的節點區間。

在做完 "galloping" 後，和填入 find run 中的方法一致，作者用 binary insertion sort 的方式，尋找節點 A[0] 在被找到的區間的插入點。不過，這次的 binary insertion sort 有搜尋次數的限制，當搜尋次數超過作者限定的上限值時，就會停止進行 galloping mode，回到原本的合併操作。

由於作者在 Python 的實作中，使用的是陣列，所以可以簡單的運用此方法做搜尋及合併。但是，在 Linux 核心，或者 lab0-c 的環境中，使用的資料結構都是鏈結串列。因此，在不管是在 galloping mode 做區間的尋找，或者是找到區間後的二元搜尋，都一定會少不了指標操作。且在第一週測驗二中，其 Tim sort 的實作和 lib/list_sort 有一個共通點，就是 merge() 和 merge_final() 兩個函式的合併實作是不同調的 – merge() 用的是指標的指標；而 merge_final() 用的是指標指向輸入的 head 鏈結串列直接操作，原因是此函式是用來將最終鏈結串列的 prev 指標建立起來。此場景增加了實作 galloping mode 的困難度。

目前我先將 galloping mode 實作於 merge() 函式中，且其在找到該元素可插入的區塊後，使用的是 linear insertion，而非原作者使用的 binary insertion。以兩個變數 gallop_cnt_a 和 gallop_cnt_b 分別掌握串列 a 和 b 誰先被連續合併超過 min_gallop 次。若有某一變數超過 min_gallop，則會啟動 galloping mode。

• 測試結果

在經過和 Minimum run size 小節中一樣的實驗後，可以得到以下的結果：

完全隨機的資料

升冪資料，隨機 3 個資料換成隨機資料

升冪資料，最後 10 個資料換成隨機資料

升冪資料，隨機 1% 個資料換成隨機資料

有多個重複的資料

Worst case scenario for merge sort

Discussion

從以上的 user space 實驗結果中，可以觀察到，除了隨機資料分佈和多個重複資料分佈以外，有 galloping mode 實作的排序運行時間，比起原本的 Tim sort，以及只實作 min run strategy 的 Tim sort，都要快。

除此之外，從排序時的比較次數分佈可以很明顯的看到，有實作 galloping mode 以及 min run 的 Tim sort，比只有實作 min run 的 Tim sort 的比較次數要少。但在部份的資料分佈中（隨機資料分佈、多個重複資料分佈、合併排序的最差資料分佈），它們的最小比較次數還是無法突破原本的 Tim sort 實作中的最小比較次數。

在 fennecJ 和 yanjiew1 的筆記中，都提到過 Tim sort 的優化型態 – Adaptive ShiversSort、和 Powersort。前者的筆記提供了實作的範例和它們在 user space 的實驗成果，其中關於 Adaptive ShiversSort 的排序穩定性吸引了我的目光，因此，接下來我嘗試將 adaptive shiverssort 的合併策略實作於有 galloping mode 以及 binary insertion sort during min run strategy 的 Tim sort 中，以了解 Adaptive ShiversSort 的合併策略是否真如同其原論文所述的這麼神奇。

Adaptive Shivers Sort: An Alternative Sorting Algorithm

一個優化 Tim sort 合併流程的排序策略。在這篇論文中，除了分析 Tim sort 以及 Adaptive ShiversSort 演算法以外，藉由 Buss and
Knop 發明的方法，證明了此演算法為 stable merge sort，也證明了一個合併排序演算法是 stable merge sort 的條件。

在此篇論文中，作者將 Shivers sort 和 Tim sort 中的特性混合，提出 Adaptive ShiversSort 的合併策略為以下：

while true:
+    if h >= 3 and l[h - 2] <= max{l[h - 1], l[h]}:
+        merge(r[h - 2], r[h - 1])
    else if runs != NULL:
        remove a run R from runs and push R onto S
    else:
        break
+while h >= 2:
+    merge(r[h - 1], r[h])

和 Tim sort 的不同之處已以 diff 標記起來。Adaptive ShiversSort 的合併策略只有兩個條件：

• 當 run 堆疊的數量超過 3 個，且前兩項（tp->prev->prev）的 run 長度比當前（tp）或當前之前一項（tp->prev） run 長度要小時：執行當前 run 指標之前兩項（tp->prev->prev 和 tp->prev）的合併。
• 當 run 堆疊的數量超過 2 個：執行當前 run 指標（tp）以及前一項 run 指標（tp->prev）的合併。

相比於 Tim sort，作者在論文中以理論的方式，證明 Adaptive ShiversSort 可以優化 Tim sort 在其最差情況的表現，也可以擁有更穩定的排序上限及下限。

此外，從虛擬碼中可以看出，Adaptive ShiversSort 的實作與 Tim sort 高度相似，因此兩者之間的實作轉換成本非常低。所以，針對原本的 Tim sort 合併實作，我只做了以下的改變：

-if ((n >= 3 &&
-     run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
-    (n >= 4 && run_size(tp->prev->prev->prev) <=
-                   run_size(tp->prev->prev) + run_size(tp->prev))) {
-    if (run_size(tp->prev->prev) < run_size(tp)) {
-        tp->prev = merge_at(priv, cmp, tp->prev);
-    } else {
-        tp = merge_at(priv, cmp, tp);
-    }
+if (n >= 3 && run_size(tp->prev->prev) <= run_size_cmp(tp, tp->prev)) {
+    tp->prev = merge_at(priv, cmp, tp->prev);

其中，run_size_cmp() 函式是用來回傳兩個輸入的串列中的最大值。

至於在

while h >= 2:
    merge(r[h - 1], r[h])

得虛擬碼實作中，由於從測驗題中引入的 Tim sort 的 run 合併實作和原本的有出入，若直接套用會額外增加許多的比較次數，因此就不做更動。

• 測試結果

測試環境一樣在 lab0-c 環境中，使用 char 作為結構體資料的資料型態。測試的項目和資料分佈和 Tim sort 的測試是一樣的。

測試結束後，可以得到以下的結果：

完全隨機的資料

升冪資料，隨機 3 個資料換成隨機資料

升冪資料，最後 10 個資料換成隨機資料

升冪資料，隨機 1% 個資料換成隨機資料

有多個重複的資料

Worst case scenario for merge sort

Discussion