--- tags: C image: https://i.imgur.com/xAE53B1.png --- # Merge Sort 與它的變化 :::info 建議先閱讀〈[你所不知道的 C 語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list)〉熟悉如何使用指標的指標以及如何用在 linked list 上還有 LeetCode 的案例探討，這會使你更好理解這篇筆記 :+1: ::: 旁聽[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FSJ3QpJJNY)錄製[作業二](https://hackmd.io/@sysprog/info2021/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Finfo2021-homework2)的時候選了 easy 的 [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/) 以及它的延伸問題 [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)，會選 Merge Two Sorted Lists 主要是因為用到指標的指標，Interviewer 應該會想知道 Interviewee 對於指標的理解程度，再加上不斷的 NG 就不斷的重寫，不斷的重寫就覺得重複寫 L1 跟 L2 很麻煩，最終發現 Merge Two Sorted Lists 可以[改良](https://leetcode.com/problems/merge-two-sorted-lists/discuss/1593917/cc-9-lines-after-refactor-pointer-to-pointer-solution-with-explanation)的地方，可惜想到的時候影片已經剪完上傳了，同時在自修 [2021 Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule?revision=f0e4420bc241aac0d928a91894b30427baa310e6)時剛好在寫的 [quiz1](https://hackmd.io/@sysprog/linux2021-quiz1)，種種機緣巧合之下才想出來這一系列的寫法。 # Merge Sort 簡介 Merge Sort 是分治法的經典案例，概念也很簡單，以串列為例，將串列分割成排序好的子串列，再將所有排序好的子串列合併在一起。 ```graphviz digraph G { compound=true node[shape=box, height=.1];sorted_1 sorted_2 sorted_3 sorted_4 sorted_5 sorted_6 sorted_7 sorted_8; node[shape=record, height=.1];input result divide_41 divide_42 divide_21 divide_22 divide_23 divide_24 merge_21 merge_22 merge_23 merge_24 merge_41 merge_42; input[label="<f0>2|<f1>5|<f2>4|<f3>6|<f4>8|<f5>1|<f6>7|<f7>3"] result[label="<f0>1|<f1>2|<f2>3|<f3>4|<f4>5|<f5>6|<f6>7|<f7>8"] divide_41[label="<f1>2|<f2>5|<f3>4|<f4>6"] divide_42[label="<f1>8|<f2>1|<f3>7|<f4>3"] divide_21[label="<f0>2|<f1>5"] divide_22[label="<f0>4|<f1>6"] divide_23[label="<f0>8|<f1>1"] divide_24[label="<f0>7|<f1>3"] sorted_1[label="1"] sorted_2[label="2"] sorted_3[label="3"] sorted_4[label="4"] sorted_5[label="5"] sorted_6[label="6"] sorted_7[label="7"] sorted_8[label="8"] merge_21[label="<f0>2|<f1>5"] merge_22[label="<f0>4|<f1>6"] merge_23[label="<f0>1|<f1>8"] merge_24[label="<f0>3|<f1>7"] merge_41[label="<f1>2|<f2>4|<f3>5|<f4>6"] merge_42[label="<f1>1|<f2>3|<f3>7|<f4>8"] subgraph cluster_0 { style=filled; color="#ef6548"; label="divide"; divide_pad[label="------------------", style=invis] divide_pad -> divide_23[style=invis] input -> divide_41 input -> divide_42 divide_41 -> divide_21 divide_41 -> divide_22 divide_42 -> divide_23 divide_42 -> divide_24 } divide_21:f0 -> sorted_2 divide_21:f1 -> sorted_5 divide_22 -> sorted_4 divide_22 -> sorted_6 divide_23:f0 -> sorted_8 divide_23:f1 -> sorted_1 divide_24:f0 -> sorted_7 divide_24:f1 -> sorted_3 subgraph cluster_1 { style=filled; color="#a6cee3"; label="sorted lists"; sorted_1; sorted_2; sorted_3; sorted_4; sorted_5; sorted_6; sorted_7; sorted_8; } sorted_2 -> merge_21:f0 sorted_5 -> merge_21:f1 sorted_4 -> merge_22:f0 sorted_6 -> merge_22:f1 sorted_8 -> merge_23:f1[constraint=false] sorted_1 -> merge_23:f0 sorted_7 -> merge_24:f1 sorted_3 -> merge_24:f0 subgraph cluster_2 { style=filled; color="#b2df8a"; label="merge"; merge_pad[label="----------------", style=invis] rank=same; merge_41; merge_pad; merge_42 rank=same; merge_41; merge_42; merge_pad; merge_22 -> merge_pad[style=invis] merge_23 -> merge_pad[style=invis] merge_pad -> result[style=invis] merge_21 -> merge_41 merge_22 -> merge_41 merge_23 -> merge_42 merge_24 -> merge_42 merge_41 -> result merge_42 -> result } } ``` 常見的 Merge Sort 是用遞迴搭配快慢指標將串列左右對半切分，直到分割成單一節點再合併成排序好的串列。 # 遞迴版 用遞迴實作 Merge Sort 可以非常的直觀表達分割與合併的過程，彷彿可以看到上圖。 ```c node_t *mergesort_list(node_t *head) { if (!head || !head->next) return head; node_t *slow = head; node_t *fast; for (fast = head->next; fast && fast->next; fast = fast->next->next) slow = slow->next; node_t *mid = slow->next; slow->next = NULL; node_t *left = mergesort_list(head); node_t *right = mergesort_list(mid); return mergeTwoLists(left, right); } void mergesort(node_t **list) { *list = mergesort_list(*list); } ``` 注意 `slow->next = NULL` 並不是把 slow 的下一個節點設為 NULL 而是 `slow->next` 指向 NULL # 迭代的實作 有句話是這麼說的 >遞迴只應天上有，凡人該當用迴圈 有時候反過來說也是正確的，像是如何把 Merge Sort 從遞迴轉成迭代。 如何將 Merge Sort 從遞迴轉成迭代？我卡在到底該如何把快慢指標將串列分割成 left 跟 right 的方式用迭代的方式去模擬出來？ 直到在做 [quiz1](https://hackmd.io/@sysprog/linux2021-quiz1) 時參考 [iLeafy11](https://hackmd.io/@qJEZpNvuSHe0kzJAmMSeQg/Sy0v_i3f_#Optimized-QuickSort-%E2%80%94-C-Implementation-Non-Recursive) 跟 [ccs100203](https://hackmd.io/@cccccs100203/linux2021-quiz1) 實作的非遞迴 quicksort 之後給我一點靈感並實做出下面的 quicksort。 利用 stack 去模擬遞迴的過程，從 stack 取出 pivot，再把比 pivot 還小的節點接在 left，反之則接在 right，之後由小到大將 `left`, `pivot`, `right` 推入 stack 變成下輪迴圈的 pivot，並重複此過程，直到沒有 `pivot->next` 的時候表示目前 `pivot` 的節點是排序好的，就把它接到 `result` 上。 ```c void quicksort_iter(node_t **list) { if (!*list || !(*list)->next) return; node_t *result = NULL; node_t *stack[10000] = {}; int top = 0; stack[top] = *list; while (top >= 0) { node_t *pivot = stack[top--]; if (pivot->next) { int value = pivot->value; node_t *p = pivot->next; pivot->next = NULL; node_t *left = NULL, *right = NULL; while (p) { node_t *cur = p; p = p->next; list_add_node_t(cur->value > value ? &right : &left, cur); } if (left) stack[++top] = left; stack[++top] = pivot; if (right) stack[++top] = right; } else list_add_node_t(&result, pivot); } *list = result; } ``` 觀察非遞迴版本 quicksort，**當 pivot 沒有 next 就接到 result 上，這就好像遞迴版的 Merge Sort 當節點無法分割就合併**，於是稍加修改就完成了迭代版的 Merge Sort。從[你所不知道的 C 語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list)得知這種合併方式是 naive 版的 [merge K Lists](https://leetcode.com/problems/merge-k-sorted-lists/) - [ ] naive 的迭代版 Merge Sort ```c void mergesort_iter(node_t **list) { node_t *head = *list; if (!head || !head->next) return; node_t *result = NULL; node_t *stack[1000]; int top = 0; stack[top] = head; while (top >= 0) { node_t *left = stack[top--]; if (left) { node_t *slow = left; node_t *fast; for (fast = left->next; fast && fast->next; fast = fast->next->next) slow = slow->next; node_t *right = slow->next; slow->next = NULL; stack[++top] = left; stack[++top] = right; } else result = mergeTwoLists(result, stack[top--]); } *list = result; } ``` naive 是將單一節點逐個合併，速度非常慢，所以改成將分割好的節點存進指標陣列 lists 改成頭尾合併來改善效能。 - [ ] improved version ```c void mergesort_iter(node_t **list) { node_t *head = *list; if (!head || !head->next) return; int top = 0; int listsSize = 0; node_t *stack[1000] = {NULL}; node_t *lists[100000] = {NULL}; stack[top] = head; // divide to single node while (top >= 0) { node_t *left = stack[top--]; if (left) { node_t *slow = left; node_t *fast; for (fast = left->next; fast && fast->next; fast = fast->next->next) slow = slow->next; node_t *right = slow->next; slow->next = NULL; stack[++top] = left; stack[++top] = right; } else lists[listsSize++] = stack[top--]; } // merge K sorted lists while (listsSize > 1) { for (int i = 0, j = listsSize - 1; i < j; i++, j--) lists[i] = mergeTwoLists(lists[i], lists[j]); listsSize = (listsSize + 1) / 2; } *list = lists[0]; } ``` 觀察改進後的 naive 版，可以把迭代版 Merge Sort 拆成**分割階段**與**合併階段**來實作與優化，進而延伸出各種組合，接下來分別探討兩種階段的實作。 回顧一下 Merge Sort 的概念，**將串列分割成排序好的子串列，再將所有排序好的子串列合併在一起。** 分割 $\to$ 將 list 分割成 sorted lists 合併 $\to$ 將 sorted lists 合併在一起 分割沒有規定一定要像遞迴一樣用快慢指標分割成單一節點，合併也沒有規定一定要用 naive 的方式來做，知道它們的目的即可，不應被常見的作法限制住思考。 為了方便測試迭代版使用不同 divide 跟 merge 的組合，還要避免寫出 `func_v1` 到 `func_vN` 的恐怖命名，最終將 Merge Sort 的介面(interface)設計成可以任意組合 divide 跟 merge 函式。 | 函式指標 | 說明 | | -------- | --------------------------------------------------------------------------------------- | | divide_f | 將傳入的 list 分割成 sorted lists 存到 lists，並更新 sorted lists 的數量到 listsSize | | merge_f | 合併 lists 到 list | ```c typedef void (divide_f)(node_t **list, node_t *lists[], size_t *listsSize); typedef void (merge_f)(node_t **list, node_t *lists[], size_t listsSize); void merge_sort_iter(node_t **list, divide_f divide, merge_f merge); ``` `merge_sort_iter` 的內部實作如下，得出 list 的長度之後配置記憶體給 lists，配置完成後執行給定的 divide 跟 merge 函式即可。 ```c void merge_sort_iter(node_t **list, divide_f divide , merge_f merge) { size_t listsSize = 0; const size_t n = get_list_length(*list); node_t *lists[n]; divide(list, lists, &listsSize); merge(list, lists, listsSize); } ``` ## 分割 分割 $\to$ 將串列分割成 sorted lists 以下方的串列為例，如果串列要遞增排序，那麼 sorted list 有兩種 case ### 分割成單一節點 ```graphviz digraph G { rankdir=LR; node[shape=record] node1[label="{<data>1|<next>}", ] node2[label="{<data>2|<next>}", ] node3[label="{<data>3|<next>}", ] node4[label="{<data>4|<next>}", ] node5[label="{<data>5|<next>}", ] node6[label="{<data>6|<next>}", ] node7[label="{<data>7|<next>}", ] node8[label="{<data>8|<next>}", ] node2:next:ref->node5:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node5:next:ref->node4:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node4:next:ref->node6:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node6:next:ref->node8:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node8:next:ref->node1:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node1:next:ref->node3:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node3:next:ref->node7:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] } ``` ```graphviz digraph G { rankdir=LR; node[shape=record] node1[label="{<data>1|<next>}", ] node2[label="{<data>2|<next>}", ] node3[label="{<data>3|<next>}", ] node4[label="{<data>4|<next>}", ] node5[label="{<data>5|<next>}", ] node6[label="{<data>6|<next>}", ] node7[label="{<data>7|<next>}", ] node8[label="{<data>8|<next>}", ] node2:next->node5:data[style=invis] node5:next->node4:data[style=invis] node4:next->node6:data[style=invis] node6:next->node8:data[style=invis] node8:next->node1:data[style=invis] node1:next->node3:data[style=invis] node3:next->node7:data[style=invis] } ``` - [ ] 快慢指標 在遞迴版的 Merge Sort 中常見的作法，用快慢指標將串列分割成單一節點，slow 走一步，fast 走兩步，一旦 fast 走訪完串列，slow 會停在串列的中間，這時候用 `right` 設為 `slow->next`，即右子串列的開頭，再把 `slow->next` 指向 `NULL` 作為左子串列的尾端便完成了分割，再將分割好的子串列放進 stack，進入下輪回圈繼續分割直到分割成單一節點再存入 lists。 ```c void fast_slow_divide(node_t **list, node_t *lists[], size_t *listsSize) { size_t i = 0; int top = 0; node_t *stack[1000] = {NULL}; stack[top] = *list; while (top >= 0) { node_t *left = stack[top--]; if (left) { node_t *slow = left, *fast; for (*fast = left->next; fast && fast->next; fast = fast->next->next) slow = slow->next; node_t *right = slow->next; slow->next = NULL; stack[++top] = left; stack[++top] = right; } else lists[i++] = stack[top--]; } *listsSize = i; } ``` - [ ] 分割成單一節點 除了用快慢指標來分割節點，也可以直接把每個節點指向 `NULL` 再放進 `lists`，程式碼直觀又簡單。 ```c void divide_to_single(node_t **list, node_t *lists[], size_t *listsSize) { size_t i = 0; for (node_t *node = *list, *next; node; node = next) { next = node->next; node->next = NULL; lists[i++] = node; } *listsSize = i; } ``` ### 分割成排序好的串列 分離出串列中排序好的部份並存入到 lists ```graphviz digraph G { rankdir=LR; node[shape=record] node1[label="{<data>1|<next>}", ] node2[label="{<data>2|<next>}", ] node3[label="{<data>3|<next>}", ] node4[label="{<data>4|<next>}", ] node5[label="{<data>5|<next>}", ] node6[label="{<data>6|<next>}", ] node7[label="{<data>7|<next>}", ] node8[label="{<data>8|<next>}", ] node2:next:ref->node5:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node5:next:ref->node4:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node4:next:ref->node6:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node6:next:ref->node8:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node8:next:ref->node1:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node1:next:ref->node3:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node3:next:ref->node7:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] } ``` ```graphviz digraph G { rankdir=LR; node[shape=record] node1[label="{<data>1|<next>}", ] node2[label="{<data>2|<next>}", ] node3[label="{<data>3|<next>}", ] node4[label="{<data>4|<next>}", ] node5[label="{<data>5|<next>}", ] node6[label="{<data>6|<next>}", ] node7[label="{<data>7|<next>}", ] node8[label="{<data>8|<next>}", ] node2:next:ref->node5:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node5:next:ref->node4:data[style=invis] node4:next:ref->node6:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node6:next:ref->node8:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node8:next:ref->node1:data[style=invis] node1:next:ref->node3:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node3:next:ref->node7:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] } ``` 跟前兩種比起來這種分割方式最大的優勢在於如果傳入的是排序好的串列，就不用進入合併階段，直接將 worst case 變成 best case，反之如果傳入的相反順序的串列則會變成 worst case，分割速度會比直接分割成單一節點的方式稍微慢一些。 #### 時間複雜度 | 分割方式 | best | average | worst | | ------------ | ---- | ------- | --- | | 單一節點 | $O(nlogn)$ | $O(nlogn)$ |$O(nlogn)$| | 排序好的串列 | $O(n)$ | $O(nlogn)$|$O(nlogn)$| #### 空間複雜度 假設 lists 是用串列而不是陣列 | 分割方式 | best | average | worst | | ------------ | ---- | ------- | --- | | 單一節點 | $O(n)$ | $O(n)$ |$O(n)$| | 排序好的串列 | $O(1)$ | $O(n)$|$O(n)$| ```c void divide_to_sorted(node_t **list, node_t *lists[], size_t *listsSize) { size_t i = 0; node_t *sorted = *list; while (sorted) { node_t *iter = sorted; while (iter && iter->next) { if (iter->value < iter->next->value) iter = iter->next; else break; } lists[i++] = sorted; sorted = iter->next; iter->next = NULL; } *listsSize = i; } ``` 若串列是遞增排序下面分別為 best & worst case - [ ] best case ```graphviz digraph G { rankdir=LR; node[shape=record] node1[label="{<data>1|<next>}", ] node2[label="{<data>2|<next>}", ] node3[label="{<data>3|<next>}", ] node4[label="{<data>4|<next>}", ] node5[label="{<data>5|<next>}", ] node6[label="{<data>6|<next>}", ] node7[label="{<data>7|<next>}", ] node8[label="{<data>8|<next>}", ] node1:next:ref->node2:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node2:next:ref->node3:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node3:next:ref->node4:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node4:next:ref->node5:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node5:next:ref->node6:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node6:next:ref->node7:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] node7:next:ref->node8:data[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false,arrowsize=1.2] } ``` - [ ] worst case ```graphviz digraph G { rankdir=LR; node[shape=record] node1[label="{<data>1|<next>}", ] node2[label="{<data>2|<next>}", ] node3[label="{<data>3|<next>}", ] node4[label="{<data>4|<next>}", ] node5[label="{<data>5|<next>}", ] node6[label="{<data>6|<next>}", ] node7[label="{<data>7|<next>}", ] node8[label="{<data>8|<next>}", ] node8:next->node7:data[style=invis] node7:next->node6:data[style=invis] node6:next->node5:data[style=invis] node5:next->node4:data[style=invis] node4:next->node3:data[style=invis] node3:next->node2:data[style=invis] node2:next->node1:data[style=invis] } ``` ## 合併 ```graphviz digraph G { result[label="1|2|3|4|5|6|7|8", shape=record, height=.1] node31[label="2|5", shape=record, height=.1] node32[label="4|6|8", shape=record, height=.1] node33[label="1|7", shape=record, height=.1] node34[label="3", shape=record, height=.1,width=.4] node41[label="2|4|5|6|8", shape=record, height=.1] node42[label="1|3|7", shape=record, height=.1] subgraph cluster_3 { style=filled; color="#a6cee3"; label="sorted lists"; node32; node34; node33; node31; } node31 -> node41 node32 -> node41 node33 -> node42 node34 -> node42 subgraph cluster_2 { style=filled; color="#b2df8a"; label="merge"; node41 node41 node42 node42 node41->result node42->result } } ``` ### 頭尾合併 從固定第一條串列改成頭跟尾兩兩合併，直到剩一條為止，比起前一方法的每次都用愈來愈長的串列跟另一條串列合併，頭尾合併在多數的情況下兩條串列的長度比較平均，合併會比較快。 當合併完頭尾後，偶數長度會少一半，奇數長度則為 (listsSize + 1) / 2，奇數更新的方式也可以用在偶數長度上。 ```c void head_tail_merge(node_t **list, node_t *lists[], size_t listsSize) { if(listsSize == 0) return; while (listsSize > 1) { for (int i = 0, j = listsSize - 1; i < j; i++, j--) lists[i] = mergeTwoLists(lists[i], lists[j]); listsSize = (listsSize + 1) / 2; } *list = lists[0]; } ``` ### 分段合併 ```graphviz digraph G { // splines=false; { node[shape=none,label="interval = 1"]; i1 node[shape=none,label="interval = 2"]; i2 node[shape=none,label="interval = 4"]; i4 node[shape=none,label="interval = 8"]; i8 } interval1[label="<f0>L0|<f1>L1|<f2>L2|<f3>L3|<f4>L4|<f5>L5|<f6>L6|<f7>L7", shape=record, fixedsize=false,width=5] interval2[label="<f0>L01|<f1>|<f2>L23|<f3>|<f4>L45|<f5>|<f6>L67|<f7>", shape=record, fixedsize=false,width=5] interval4[label="<f0>L0123|<f1>|<f2>|<f3>|<f4>L4567|<f5>|<f6>|<f7>",shape=record, fixedsize=false,width=5] interval8[label="<f0>result|<f1>|<f2>|<f3>|<f4>|<f5>|<f6>|<f7>", shape=record, fixedsize=false,width=5] i1->i2[style=invis] i2->i4[style=invis] i4->i8[style=invis] interval1:f0 -> interval2:f0 interval1:f1 -> interval2:f0 interval1:f2 -> interval2:f2 interval1:f3 -> interval2:f2 interval1:f4 -> interval2:f4 interval1:f5 -> interval2:f4 interval1:f6 -> interval2:f6 interval1:f7 -> interval2:f6 interval1:f7 -> interval2:f7[style=invis] interval2:f0 -> interval4:f0 interval2:f2 -> interval4:f0 interval2:f4 -> interval4:f4 interval2:f6 -> interval4:f4 interval2:f7 -> interval4:f7[style=invis] interval4:f0 -> interval8:f0 interval4:f4 -> interval8:f0 interval4:f7 -> interval8:f7[style=invis] } ``` 除了頭尾合併，還可以分段存取下個要合併的串列，分別合併 `lists[i]` 跟 `lists[i + interval]`，為確保內層迴圈不會重複存取，索引值 `i` 會更新為 `i + interval * 2`，當內層迴圈合併完之後會把解果分別存到 `lists[interval*2]`, `lists[interval*4]`, `lists[interval*6]` ```c void interval_merge(node_t **list, node_t *lists[], size_t listsSize) { if(listsSize == 0) return; for (int interval = 1; interval < listsSize; interval *= 2) for (int i = 0; i + interval < listsSize; i += interval * 2) lists[i] = mergeTwoLists(lists[i], lists[i + interval]); *list = lists[0]; } ``` ### Divide and Conquer lists 中的串列是排序好的，可以視為 sorted element，直接把 lists 當作陣列版的 merge sort 來做即可 ```c static node_t* merge_lists(node_t **lists, int low, int high) { if(low > high) return NULL; if(low == high) return lists[low]; int mid = (low + high) / 2; node_t *left = merge_lists(lists, low, mid); node_t *right = merge_lists(lists, mid + 1, high); return mergeTwoLists(left, right); } void divide_and_conquer(node_t **list, node_t *lists[], size_t listsSize) { *list = merge_lists(lists, 0, listsSize - 1); } ``` # 效能測試 [GitHub](https://github.com/LambertWSJ/Modified-Merge-Sort) 連結 編譯器優化在 `O3` 的情況下分別針對 Merge 跟 Divdie 做 Benchmark，每次執行 1000 回合，每回合排序長度為10萬組的串列，串列分別有三種 case * 順序打亂的串列 * 已排序好的串列 e.g. `1->2->3->4->5` * 順序相反的串列 e.g. `5->4->3->2->1` 測試 Divide 的時候只使用 Merge 的分段合併 測試 Merge 的時候只使用 Divide 的分割成單一節點 由於之前[測試](https://hackmd.io/FnwoqDSARLGZI_diVtfVKg?view)的時候發現頭尾合併跟分段合併執行時間都差不多，但是一起跑的時候分段合併就是快一些，所以這次改成無論是測試 Divide 還是測試 Merge，我都先個別做 Benchmark 紀錄執行時間再繪圖，之後在全部一起做 Benchmark 跟繪圖，兩著沒有相差太多才一起做 Benchmark，下方的圖形皆為檢查後沒問題後全部一起做 Benchmark 的結果，建議用自己的電腦測試看看各種組合。 ## Divide #### 順序打亂的串列 順序打亂的情況下，分割成單一節點與分割出 sorted lists 的效能差不多，而使用快慢指標來分割的方式則是最慢的 ![](https://i.imgur.com/zPjz2wH.png) #### 排序好的串列 跟預期的一樣，分割出 sorted lists 的效能，會遠比其它分割方式還要快許多，只要走訪完串列就會離開不會執行合併的動作，因此省下大量的時間，其它的分割方式無論串列是否已排序都會完整執行完全部的流程。 從順序打亂的情況下得知， div-sorted 跟 div-single 相差無幾，那麼下圖的 div-sorted 可以大致視為分割階段的執行時間，div-single 跟 div-sorted 間的差距即合併的執行時間，可見合併是最耗時的任務，因此優化 merge 是勝出的關鍵。 ![](https://i.imgur.com/8mDo7wH.png) #### 順序相反的串列 即便在 worst case 的情況下，分割出 sorted lists 的速度稍微比直接切割成單一節點慢一些些，這出乎我意料之外，我本以為 div-sorted 會更慢。 ![](https://i.imgur.com/7S8ZJDn.png) ## Merge 順序打亂也就是常見的情況下，使用分治法會比其它合併方式還要快，而如果是排序好的或是順序相反的串列，頭尾合併會變成最慢，而分段合併會比分治法還要再更快一些些。 在排序好的情況下(無論是遞增還是遞減)，頭尾合併每次 merge 的時候要走訪完整條串列，也就是 Merge Two Sorted Lists 的最差情況，而分段合併跟分治法的合併順序大致相同，差在後者會先把左子串列合併完畢才合併右子串列，但都會和鄰近的串列合併，也比較少機會碰到最差情況。 #### 順序打亂的串列 ![](https://i.imgur.com/KHIPH5E.png) #### 排序好的串列 ![](https://i.imgur.com/9XfmesA.png) #### 順序相反的串列 ![](https://i.imgur.com/FgJkGBX.png) ## 與遞迴版比較 透過做實驗比較 Divide 跟 Merge 函式的效能後，Divide 選擇用分割出排序好的串列，Merge 選擇用分治法這兩種組合來跟遞迴版的 Merge Sort 比較，改良後的迭代版 Merge Sort 都遠比一般的遞迴版還快上許多。 - [ ] 順序打亂的串列 ![](https://i.imgur.com/8AWAkdY.png) - [ ] 排序好的串列 ![](https://i.imgur.com/av4C34y.png) - [ ] 順序相反的串列 ![](https://i.imgur.com/QDYcGSY.png)