Merge Sort 與它的變化

建議先閱讀〈你所不知道的 C 語言: linked list 和非連續記憶體操作〉熟悉如何使用指標的指標以及如何用在 linked list 上還有 LeetCode 的案例探討，這會使你更好理解這篇筆記

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

旁聽資訊科技產業專案設計錄製作業二的時候選了 easy 的 Merge Two Sorted Lists 以及它的延伸問題 Merge k Sorted Lists，會選 Merge Two Sorted Lists 主要是因為用到指標的指標，Interviewer 應該會想知道 Interviewee 對於指標的理解程度，再加上不斷的 NG 就不斷的重寫，不斷的重寫就覺得重複寫 L1 跟 L2 很麻煩，最終發現 Merge Two Sorted Lists 可以改良的地方，可惜想到的時候影片已經剪完上傳了，同時在自修 2021 Linux 核心設計時剛好在寫的 quiz1，種種機緣巧合之下才想出來這一系列的寫法。

Merge Sort 簡介

Merge Sort 是分治法的經典案例，概念也很簡單，以串列為例，將串列分割成排序好的子串列，再將所有排序好的子串列合併在一起。

常見的 Merge Sort 是用遞迴搭配快慢指標將串列左右對半切分，直到分割成單一節點再合併成排序好的串列。

遞迴版

用遞迴實作 Merge Sort 可以非常的直觀表達分割與合併的過程，彷彿可以看到上圖。

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 時參考 iLeafy11 跟 ccs100203 實作的非遞迴 quicksort 之後給我一點靈感並實做出下面的 quicksort。

利用 stack 去模擬遞迴的過程，從 stack 取出 pivot，再把比 pivot 還小的節點接在 left，反之則接在 right，之後由小到大將 left, pivot, right 推入 stack 變成下輪迴圈的 pivot，並重複此過程，直到沒有 pivot->next 的時候表示目前 pivot 的節點是排序好的，就把它接到 result 上。

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 和非連續記憶體操作得知這種合併方式是 naive 版的 merge K Lists

naive 的迭代版 Merge Sort

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

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

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 函式即可。

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

分割成單一節點

快慢指標

在遞迴版的 Merge Sort 中常見的作法，用快慢指標將串列分割成單一節點，slow 走一步，fast 走兩步，一旦 fast 走訪完串列，slow 會停在串列的中間，這時候用 right 設為 slow->next，即右子串列的開頭，再把 slow->next 指向 NULL 作為左子串列的尾端便完成了分割，再將分割好的子串列放進 stack，進入下輪回圈繼續分割直到分割成單一節點再存入 lists。

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，程式碼直觀又簡單。

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

跟前兩種比起來這種分割方式最大的優勢在於如果傳入的是排序好的串列，就不用進入合併階段，直接將 worst case 變成 best case，反之如果傳入的相反順序的串列則會變成 worst case，分割速度會比直接分割成單一節點的方式稍微慢一些。

時間複雜度

分割方式	best	average	worst
單一節點	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$
排序好的串列	$O (n)$	$O (n l o g n)$	$O (n l o g n)$

空間複雜度

假設 lists 是用串列而不是陣列

分割方式	best	average	worst
單一節點	$O (n)$	$O (n)$	$O (n)$
排序好的串列	$O (1)$	$O (n)$	$O (n)$

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

worst case

合併

頭尾合併

從固定第一條串列改成頭跟尾兩兩合併，直到剩一條為止，比起前一方法的每次都用愈來愈長的串列跟另一條串列合併，頭尾合併在多數的情況下兩條串列的長度比較平均，合併會比較快。

當合併完頭尾後，偶數長度會少一半，奇數長度則為 (listsSize + 1) / 2，奇數更新的方式也可以用在偶數長度上。

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];
}

分段合併

除了頭尾合併，還可以分段存取下個要合併的串列，分別合併 lists[i] 跟 lists[i + interval]，為確保內層迴圈不會重複存取，索引值 i 會更新為 i + interval * 2，當內層迴圈合併完之後會把解果分別存到 lists[interval*2], lists[interval*4], lists[interval*6]

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 來做即可

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 連結

編譯器優化在 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 的分割成單一節點

由於之前測試的時候發現頭尾合併跟分段合併執行時間都差不多，但是一起跑的時候分段合併就是快一些，所以這次改成無論是測試 Divide 還是測試 Merge，我都先個別做 Benchmark 紀錄執行時間再繪圖，之後在全部一起做 Benchmark 跟繪圖，兩著沒有相差太多才一起做 Benchmark，下方的圖形皆為檢查後沒問題後全部一起做 Benchmark 的結果，建議用自己的電腦測試看看各種組合。

Divide

順序打亂的串列

順序打亂的情況下，分割成單一節點與分割出 sorted lists 的效能差不多，而使用快慢指標來分割的方式則是最慢的

排序好的串列

跟預期的一樣，分割出 sorted lists 的效能，會遠比其它分割方式還要快許多，只要走訪完串列就會離開不會執行合併的動作，因此省下大量的時間，其它的分割方式無論串列是否已排序都會完整執行完全部的流程。

從順序打亂的情況下得知， div-sorted 跟 div-single 相差無幾，那麼下圖的 div-sorted 可以大致視為分割階段的執行時間，div-single 跟 div-sorted 間的差距即合併的執行時間，可見合併是最耗時的任務，因此優化 merge 是勝出的關鍵。

順序相反的串列

即便在 worst case 的情況下，分割出 sorted lists 的速度稍微比直接切割成單一節點慢一些些，這出乎我意料之外，我本以為 div-sorted 會更慢。

Merge

順序打亂也就是常見的情況下，使用分治法會比其它合併方式還要快，而如果是排序好的或是順序相反的串列，頭尾合併會變成最慢，而分段合併會比分治法還要再更快一些些。

在排序好的情況下(無論是遞增還是遞減)，頭尾合併每次 merge 的時候要走訪完整條串列，也就是 Merge Two Sorted Lists 的最差情況，而分段合併跟分治法的合併順序大致相同，差在後者會先把左子串列合併完畢才合併右子串列，但都會和鄰近的串列合併，也比較少機會碰到最差情況。

順序打亂的串列

排序好的串列

順序相反的串列

與遞迴版比較

透過做實驗比較 Divide 跟 Merge 函式的效能後，Divide 選擇用分割出排序好的串列，Merge 選擇用分治法這兩種組合來跟遞迴版的 Merge Sort 比較，改良後的迭代版 Merge Sort 都遠比一般的遞迴版還快上許多。

順序打亂的串列
排序好的串列
順序相反的串列

Merge Sort 與它的變化

Merge Sort 簡介

遞迴版

迭代的實作

分割

分割成單一節點

分割成排序好的串列

時間複雜度

空間複雜度

合併

頭尾合併

分段合併

Divide and Conquer

效能測試

Divide

順序打亂的串列

排序好的串列

順序相反的串列

Merge

順序打亂的串列

排序好的串列

順序相反的串列

與遞迴版比較

Read more

Tinker-V

2025q1 Homework2 (quiz1+2)

2025q1 Homework1 (lab0)

2023q1 Homework (quiz1)