主講人: jserv / 課程討論區: 2025 年系統軟體課程
返回「Linux 核心設計」課程進度表Image Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
合併方式是當有 \(3 \times 2^k\) 個節點時，合併前兩個 \(2^k\) 變成 \(2^{k + 1}\)，並留下一個 \(2^k\) 不動，維持著合併：不合併為 2 : 1 的比例，因為只要 \(3 \times 2^k\) 可以放得進 L1 cache，可以避免 cache thrashing。
count 為 pending list 中節點的數量，在 count 變 count + 1 後，可以觀察到第 k 個位元會改為 1，0 ~ k - 1 個 bit 會變 0，此時會將 2 個 \(2^k\) 合併，並留下一個 \(2^k\)。
每當 count + 1，可能會有兩種情況：
count + 1 後為 \(2^k\)，就不合併（只有 leading 1 是 1，其餘都為 0）count = 1（\(0001_2\)）count + 1 = 2（\(0010_2\)）count + 1 為 2 是 2 的冪，所以此種情況不合併。count = 2（\(0010_2\)）count + 1 = 3（\(0011_2\)）count + 1 為 3 不是 2 的冪，所以此種情況要合併。count 變 count + 1 後，第 k 個 bit 會改為 1，0 ~ k - 1 個 bit 會變 0。而這裡的 k 為 0，所以會將 2 個 \(2^0\) 合併，並留下一個 \(2^0\)，也就是合併 2 個 1 為 2，留一個 1 不合併。以下是 count 從 0 一直加到 16 merge 的狀況：
（括號內是當次被合併的節點加起來的節點數量，用 \(\gets\) 表示串列 prev 的方向，黃色底則是告知此次合併的是 1 + 1, 2 + 2 或 4 + 4 等。）
| count 變化 | count 二進位 | merge | pending 上的節點 |
|---|---|---|---|
| 0 \(\to\) 1 | 0000 \(\to\) 0001 | no（\(2^0\)） | 1 |
| 1 \(\to\) 2 | 0001 \(\to\) 0010 | no（\(2^1\)） | 1 \(\gets\) 1 |
| 2 \(\to\) 3 | 0010 \(\to\) 0011 | yes | (2) \(\gets\) 1 |
| 3 \(\to\) 4 | 0011 \(\to\) 0100 | no（\(2^2\)） | 2 \(\gets\) 1 \(\gets\) 1 |
| 4 \(\to\) 5 | 0100 \(\to\) 0101 | yes | 2 \(\gets\) (2) \(\gets\) 1 |
| 5 \(\to\) 6 | 0101 \(\to\) 0110 | yes | (4) \(\gets\) 1 \(\gets\) 1 |
| 6 \(\to\) 7 | 0110 \(\to\) 0111 | yes | 4 \(\gets\) (2) \(\gets\) 1 |
| 7 \(\to\) 8 | 0111 \(\to\) 1000 | no（\(2^3\)） | 4 \(\gets\) 2 \(\gets\) 1 \(\gets\) 1 |
| 8 \(\to\) 9 | 1000 \(\to\) 1001 | yes | 4 \(\gets\) 2 \(\gets\) (2) \(\gets\) 1 |
| 9 \(\to\) 10 | 1001 \(\to\) 1010 | yes | 4 \(\gets\) (4) \(\gets\) 1 \(\gets\) 1 |
| 10 \(\to\) 11 | 1010 \(\to\) 1011 | yes | 4 \(\gets\) 4 \(\gets\) (2) \(\gets\) 1 |
| 11 \(\to\) 12 | 1011 \(\to\) 1100 | yes | (8) \(\gets\) 2 \(\gets\) 1 \(\gets\) 1 |
| 12 \(\to\) 13 | 1100 \(\to\) 1101 | yes | 8 \(\gets\) 2 \(\gets\) (2) \(\gets\) 1 |
| 13 \(\to\) 14 | 1101 \(\to\) 1110 | yes | 8 \(\gets\) (4) \(\gets\) 1 \(\gets\) 1 |
| 14 \(\to\) 15 | 1110 \(\to\) 1111 | yes | 8 \(\gets\) 4 \(\gets\) (2) \(\gets\) 1 |
| 15 \(\to\) 16 | 1111 \(\to\) 10000 | no（\(2^4\)） | 8 \(\gets\) 4 \(\gets\) 2 \(\gets\) 1 \(\gets\) 1 |
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
merge 函式可以看到 priv 會被當作 cmp 的參數傳入，在其他地方不會用到。q_sort 傳入的參數一樣list 指向 head 的第一個節點，pending 指向 NULL，先檢查是否沒有任何元素或只有一個元素，然後將 head 前一個節點指向的下一個位置指向 NULL，將雙向 linked list 變成單向。
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
在 while 迴圈中，會先讓 tail 往前移動到待 merge 的節點，然後在 if 判斷是否需要 merge，最後移動 pending 和 list 的位置，直到 list 沒有節點。pending 從沒有節點，然後一次次將節點從 list 中搬到 pending，等到 list 沒有節點就代表現階段結束了。
...
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
}
EXPORT_SYMBOL(list_sort);
__attribute__((nonnull(2, 3, 4))) static struct list_head *
merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)
{
// cppcheck-suppress unassignedVariable
struct list_head *head, **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
當 cmp(priv, a, b) <= 0 表示 a 的值小於 b，因為由小排序到大，所以先接 a 再接 b，cmp(priv, a, b) > 0 表示 a 的值大於 b，則是先接 b 再接 a。
其中 head 會在排序過 list 的最前面，並回傳回去。
以 4, 3, 2, 1 的 list 為例，進行 list_sort 排序，隨著 count 增加，pending 內節點數量漸漸增加，而 list 內的節點數量漸漸減少：
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
head:right:e -> node4:w
node4:left:w -> head:e
node4:right:e -> node3:w
node3:left:w -> node4:e
node3:right:e -> node2:w
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node4:n
}
list->prev = pending 因為 pending 為 NULL，所以 list->prev 也指向 NULL：digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w
node3:left:w -> node4:e
node3:right:e -> node2:w
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node4:n
}
pending->next = NULL：digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:left:w -> node4:e
node3:right:e -> node2:w
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node3:n
pending -> node4:n
tail -> pending:n
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:left:w -> node4:e
node3:right:e -> node2:w
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node3:n
pending -> node4:n
tail -> node4:left:s
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:left:w -> node4:e
node3:right:e -> node2:w[color="white"]
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node2:n
pending -> node3:n
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
a [label="a", style="normal", color="white"]
b [label="b", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:left:w -> node4:e
node3:right:e -> node2:w[color="white"]
node3:right:e -> node4:e
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node2:n
pending -> node3:n
tail -> pending
a -> node3:n
b -> node4:n
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
a [label="a", style="normal", color="white"]
b [label="b", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:right:e -> node2:w[color="white"]
node3:right:e -> node4:e
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node2:n
pending -> node3:n
tail -> pending
a -> node3:n
b -> node4:n
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:right:e -> node2:w[color="white"]
node3:right:s -> node4:e
node2:left:w -> node3:e
node2:right:e -> node1:w[color="white"]
node1:left:w -> node2:e
list -> node1:n
pending -> node2:n
tail -> pending
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:right:e -> node2:w[color="white"]
node3:right:s -> node4:e
node2:left:w -> node3:e
node2:right:e -> node1:w[color="white"]
node1:left:w -> node2:e
list -> node1:n
pending -> node2:n
tail -> node3:left:s
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:right:e -> node2:w[color="white"]
node3:right:s -> node4:e
node2:left:w -> node3:e
node2:right:e -> node1:w[color="white"]
node1:left:w -> node2:e
pending -> node1:n
tail -> node3:left:s
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
next [label="next", style="normal", color="white"]
a [label="a", style="normal", color="white"]
b [label="b", style="normal", color="white"]
head:right:e -> node1:w
node4:right:e -> node3:w[color="white"]
node3:right:e -> node2:w[color="white"]
node3:right:s -> node4:e
node2:left:w -> node3:e
node1:left:w -> head:e
pending -> node2:n
next -> node3:n
list -> node1:n
a -> node2:n
b -> node1:n
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
next [label="next", style="normal", color="white"]
a [label="a", style="normal", color="white"]
b [label="b", style="normal", color="white"]
head:right:e -> node1:w
node4:right:e -> node3:w[color="white"]
node3:right:e -> node2:w[color="white"]
node3:right:s -> node4:e
node2:left:w -> node3:e
node1:left:w -> head:e
pending -> node2:n
next -> node3:n
list -> node1:n
tail -> node1:n
a -> node2:n
b -> node2:n
}
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail [label="tail", style="normal", color="white"]
next [label="next", style="normal", color="white"]
a [label="a", style="normal", color="white"]
b [label="b", style="normal", color="white"]
head:right:e -> node1:w
node1:left:w -> head:e
node1:right:e -> node2:w
node2:left:w -> node1:e
node2:right:e -> node3:w
node3:left:w -> node2:e
node3:right:e -> node4:w
node4:left:w -> node3:e
list -> node1:n
pending -> node2:n
a -> node2:n
b -> node4:n
tail -> node4:n
}
graph TD;
LIST_SORT_C["list_sort.c"] --> LIST_SORT_H["list_sort.h"] --> TYPES_H["type.h"];
LIST_SORT_C --> CONTAINER_OF_H["container_of.h"];
LIST_SORT_C --> LIST_H["list.h"];
LIST_H --> CONTAINER_OF_H;
LIST_H --> TYPES_H["type.h"];
TYPES_H --> UAPI_TYPES_H["uapi/type.h"];
UAPI_TYPES_H --> ASM_TYPES_H["asm/type.h"];
探討 lib/list_sort.c 相關實作時，除了觀察程式碼，，也該理解為何 Linux 核心開發者採用這段程式碼，也就是推敲開發是如何思考及進行取捨。我們可參見 github commit history，lib/list_sort.c 最近一次演算法上的改動在 2019 年 5 月 15 日的 commit b5c56e0c, lib/list_sort: optimize number of calls to comparison function 引入，其中引用三篇論文：
對於比較次數的探討，我們可寫成以下形式：
\begin{gather*}
nlog_2 n - Kn + O(1)
\end{gather*}
其中，以下 merge sort 的變形 (variants)，領導係數 (leading coefficient) 皆為 \(\log_2 (n!)\)，探討的著重點在於一次項係數 K。
開發者探討 merge sort 的三種實作方式，分別為 top-down mergesort、bottom-up mergesort 和 queue-mergesort，以及開發者提出的方式，以下簡述不同的實作方式：
1. Top-down mergesort
下圖例子是 balanced power-of-2 rule dividing strategy:
digraph G {
splines=line
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;
node[shape=none];merge_pad
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"]
merge_pad[label=""]
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:f0 -> sorted_4
divide_22:f1 -> sorted_6
divide_23:f0 -> sorted_8
divide_23:f1 -> sorted_1
divide_24:f0 -> sorted_7
divide_24:f1 -> sorted_3
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
sorted_1 -> merge_23:f0
sorted_7 -> merge_24:f1
sorted_3 -> merge_24:f0
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
}
2. Bottom-up mergesort
digraph G {
splines=line
node[shape=record, height=.1];input result
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"]
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"]
input:f0 -> merge_21:f0
input:f1 -> merge_21:f1:n
input:f2 -> merge_22:f0
input:f3 -> merge_22:f1
input:f4 -> merge_23:f1
input:f5 -> merge_23:f0
input:f6 -> merge_24:f1
input:f7 -> merge_24:f0:n
merge_21:f0 -> merge_41:f1
merge_21:f1 -> merge_41:f3
merge_22:f0 -> merge_41:f2
merge_22:f1 -> merge_41:f4
merge_23:f0 -> merge_42:f1
merge_23:f1 -> merge_42:f4
merge_24:f0 -> merge_42:f2
merge_24:f1 -> merge_42:f3
merge_41:f1 -> result:f1
merge_41:f2 -> result:f3
merge_41:f3 -> result:f4
merge_41:f4 -> result:f5
merge_42:f1 -> result:f0
merge_42:f2 -> result:f2
merge_42:f3 -> result:f6
merge_42:f4 -> result:f7
}
3. Queue-mergesort
根據 [3] 的演算法，虛擬碼如下
queue-mergesort(Q):
while (Q.size != 1) do
Q.put(Merge(Q.get, Q.get))
4. lib/list_sort.c
如果查看更之前的版本 commit 043b3f7b 會發現是用 bottom-up mergesort 實作。
前提：所有子串列其長度皆為 2 的冪，所有合併皆為同大小串列。
設 \(t_i\) 為目前長度小於 \(2^i\) 的所有子串列的節點數總和。\(i\) 為正整數。
第一點：
證明當 \(t_i\) 從 \(3\times2^{i-1}-1\) 加一變成 \(3\times2^{i-1}\) 時，不存在正整數 \(j \neq i\) 使得 \(t_j\) = \(3\times2^{j-1}\) 。
假設存在 \(j>i\) 且 \(t_j\) = \(3\times2^{j-1}\) 。則有一個正整數 \(l\) 使得 \(3\times2^{i-1} + l = 3\times2^{j-1}\) 。因為長度小於 \(2^{i}\) 的所有子串列的節點數總和都包含在 \(t_i\) 裡面了，所以 \(l\) 都在長度大於等於 \(2^i\) 的串列裡。因此可以把 \(l\) 寫成 \(A\times2^i\) 。其中 A 等於任意正整數。
\(3\times2^{i-1} + A\times2^i = 3\times2^{j-1}\)
\((3+2A)\times2^{i-1} = 3\times2^{j-1}\)
\(\dfrac{(3+2A)}{3} = 2^{j-i}\)
\(1+\dfrac{2A}{3} = 2^{j-i}\) 令 \(A = 3B\) 代入，\(B\) 為任意正整數。
\(1+2B = 2^{j-i}\) 因為 \(j>i\) ，所以 \(2^{j-i}\) 必為偶數，不存在任何正整數 \(B\) 使得 \(1+2B\) 等於偶數，假設不成立，因此不存在 \(j>i\) 且 \(t_j\) = \(3\times2^j\) 。
假設存在 \(j<i\) 且 \(t_j\) = \(3\times2^{j-1}\) 。則有一個正整數 \(l\) 使得 \(3\times2^{i-1} = 3\times2^{j-1}+l\) 。因為長度小於 \(2^{j}\) 的所有子串列的節點數總和都包含在 \(t_j\) 裡面，所以 \(l\) 都在長度大於等於 \(2^j\) 的串列裡。因此可將 \(l\) 寫成 \(A\times2^j\) 。其中 \(A\) 等於任意正整數。
\(3\times2^{i-1} = 3\times2^{j-1} + A\times2^j\)
\(3\times2^{i-1} = (3+2A)\times2^{j-1}\)
\(\dfrac{(3+2A)}{3} = 2^{i-j}\)
\(1+\dfrac{2A}{3} = 2^{i-j}\) 令 \(A = 3B\) 代入，\(B\) 為任意正整數。
\(1+2B = 2^{i-j}\) 因為 \(j<i\) ，所以 \(2^{i-j}\) 必為偶數，不存在任正整數 \(B\) 使得 \(1+2B\) 等於偶數，假設不成立，因此不存在 \(j<i\) 且 \(t_j\) = \(3\times2^j\) 。
總和上述兩點，可得證。
第二點：
證明在 "能保持差異最大 \(2:1\) 的情況下，能合併則合併。" 的條件下，當\(t_{n+1}\) 從 \(3\times2^n-1\) 增加到 \(3\times2^n\) 時，一定存在兩個長度為 \(2^n\) 的子串列可供合併。
當 \(n = 0\)，因為長度最短為 1， \(3\times2^0\) = 3，長度分別為 1,1,1 ，因此可以合併，成立。
設當 \(n = k\) 時成立，則當 n = k+1 時，必須證明當 \(t_{k+2}\) 增加到 \(3\times2^{k+1}\) 時，一定存在兩個長度為 \(2^{k+1}\) 的子串列可合併。
第一個 \(2^{k+1}\) 子串列在 \(t_{k+1}\)來到 \(3\times2^k\) 時根據假設誕生。此時 \(t_{k+2}\) 也等於 \(3\times2^k\) ，合併後 \(t_{k+2}\) = \(3\times2^k\)，\(t_{k+1}\) = \(2^k\) 。
第二個 \(2^{k+1}\) 子串列在 \(t_{k+1}\)再次來到 \(3\times2^k\) 時根據假設誕生，此時 \(t_{k+2}\) 來到 \(5\times2^k\) 。
由上述兩點可知，在 \(t_{k+2}\) 從 0 增加到 \(3\times2^{k+1}\) 的過程中，一定會經過 \(3\times2^k\) 以及 \(5\times2^k\) ，並在這兩時刻產生出長度為 \(2^{k+1}\) 的串列。所以當 \(t_{k+2}\) 增加到 \(6\times2^{k} = 3\times2^{k+1}\) 時，一定存在兩個長度為 \(2^{k+1}\) 的子串列可供合併，根據數學歸納法得證。
第三點：
證明 \(2^i\) 長度串列的合併(兩個 \(2^{i-1}\) 合併成 \(2^i\))只會發生在 \(t_i\) 變成 \(3\times2^{i-1}\) 。
由第二點可知，對所有自然數 \(i\) ，\(t_i\) 不會超過 \(3\times 2^{i-1}\) ，因為只要等於 \(3\times2^{i-1}\) 就會合併串列並變回 \(2^{i-1}\) 。所以合併不會發生在 \(t_i > 3\times2^{i-1}\) 。
當 \(t_i < 3\times 2^{i-1}\) ，此時合併成 \(2^i\) 串列無法保證兩條串列比例差異不會超過 \(2:1\) ，所以不會合併。
故合併只會發生在 \(t_i = 3\times 2^{i-1}\) 得證。
綜合上述三點，可得出當 count 增加到 count+1 ，最多只會存在一正整數 \(i\) 使得 \(t_i\) 為 \(3\times 2^{i-1}\) 。若此 \(i\) 存在，則一定可合併成長度為 \(2^i\) 的串列，且此串列為此時合併的唯一串列。
每次 count 遞增所合併的串列也不會造成更長串列的連鎖合併，因為合併成 \(2^i\) 只會改變 \(t_i\) 的值，不會改變其他的 \(t\) 值，所以不會有其他 \(t_j\) 增加成 \(3\times 2^{j-1}\) 而造成合併。
list_sort 中串列大小的比例差距限制是 \(2:1\)因為目的是為了避免合併差距過大，因此使用 \(2:1\)，而非 \(3:1\) 或 \(4:1\) 呢？需要一併考慮為何不用 \(3:2\) 或 \(4:3\) 這種比例。
以下簡述 list_sort 的演算法：
第一階段：
將節點一個一個讀取，如果確定合併的大小不會超過整體的特定比例，就將之前的串列合併。因為本質還是 bottom up merge sort ，所以此階段的合併都是同大小，所有子串列也都會是 2 的冪。
第二階段：
當所有節點都讀進並盡可能的同大小合併後，就來到必須合併不同大小的階段。這個階段會將子串列由小大到一個接一個合併。
從以上兩階段可以看出，因為第一階段都是 2 的冪，在維持 \(2m : 2m+1\) 比例的情況下，第一階段結束時最大的子串列就是 \(2^{\lfloor \log_2{2mn}/{(2m+1)} \rfloor}\) 。
論文〈The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules〉提及:
Note that \(2^{\lfloor log_22n/3 \rfloor}\) is the unique power of two lying between \(n/3\) and \(2n/3\) and that the choice of rationals other than \(2/3\) will not be more balanced. For example, if \(2^{\lfloor log_2n/2 \rfloor}\) or \(2^{\lfloor log_25n/9 \rfloor}\) then the sizes of two subproblems are \((2,5)\) for \(n = 7\) while the balanced power-of-two gives \((3,4)\).
這段話其實不精準，因為當 \(n = 3\times 2^k\) 時， 在包括的情況下介於 \(n/3\) 以及 \(2n/3\) 的 2 的冪會有兩個，再不包括的情況下卻又會不存在。如果是寫成
\(n/3 < 2^{\lfloor log_22n/3 \rfloor} \leq 2n/3\)
就符合這段話的描述。進一步歸納: \(2^{\lfloor log_22n/3 \rfloor}\) 可找到最接近 \(n/2\) 的 2 的冪。
如果今天是用 \(2^{\lfloor log_23n/5 \rfloor}\) 去求 \(2^k\) ，則當 \(n = 13\) 時，\(2^{\lfloor log_23n/5 \rfloor} = 4\)，而最接近 \(13/2\) 的 2 的冪卻是 \(8\) 。
這代表如果在第一階段用 \(3:2\) 的比例去限制，在第二階段合併中，最後一次合併會是 \(9:4\) ，這個比例差距已超過第一階段的 \(3:2\) ，而同樣的反例在 \(2m:2m+1 , m>2\) 中也都會發生。因此這樣的演算法只能用在 \(2:1\) 的情況。
list_sort 的演算法是 optimal mergesortoptimal merge sort 定義：在最差的情況下，比較次數小於等於所有其他 mergesort 。
對所有 mergesort ，都可以繪製出一個 merge tree 來表示其合併的順序及長度，每一個節點的權重代表當下的串列長度。方形的是 external node (leaf) ，圓形的是 internal node 。如下圖所示：
digraph BST {
node [fontname="Arial" ];
l1 [ label = "5" ];
l21 [ label = "3" ];
l22 [ label = "2" ];
l31 [ label = "2" ];
l32 [shape=rect label = "1" ];
l33 [shape=rect label = "1" ];
l34 [shape=rect label = "1" ];
l41 [shape=rect label = "1" ];
l42 [shape=rect label = "1" ];
l1 -> { l21 l22 };
l21 -> { l31 l32 };
l22 -> { l33 l34 };
l31 -> { l41 l42 };
}
internal node 的數量為 leaf 數減一。在最差的情況下，合併 (x,y) 的次數為 x+y-1 ，因此最差情況下總共的比較次數就是
\(\sum\limits_{v}^{T}({w(v)} - 1) = \sum\limits_{v}^{T}{w(v)} - (n-1)\)
其中 \(n\) 為這次排序的節點總數，也是 leaf 的總數。而 \(v\) 為所有的 internal node 。\(w(v)\) 為該 internal node 的權重（也就是長度）。在這邊因為對所有 合併排序 n - 1 都是固定的，所以只要看 \(\sum\limits_{v}^{T}{w(v)}\) 就好。
論文〈Queue-Mergesort〉提及:
We use the fact that the weight of a merge tree is equal to its external path length. The height h(f) of a node I in a tree is the distance of a path from 1 to the root. The external path length of a tree T’ is the sum E(T’) = \(\sum\limits_{l\ a\ leaf\ of\ T'}{h(l)}\)
及以下：
Thus a merge tree T describes an optimal merge-sort on n items if and only if T has minimum external path length \(\sum\limits_{l\ a\ leaf}{h(l)}\). It is known that this occurs if and only if the following condition is satisfied: all of T’s leaves are located on its bottom two levels.
因此可知，只要證明 list_sort 的 merge tree 符合所有 leaf 都在最下面兩層這個條件，就可以證明它是 optimal merge sort 。
分析 list_sort 的演算法，可以得出以下兩點：
證明合併過程中對所有長度 n 的子串列，其 merge tree 的所有 leaf 都在最下面兩層。
證明過程：
第一階段所有合併皆為 2 的冪，符合命題。
用數學歸納法證明第二階段：
最小端的子串列只可能是 (1,1) 或 (1,2)，兩者合併都符合命題。
對第二階段過程中的任意合併，假設其兩個子串列都符合命題。
則合併的過程中，由第一點可知，其中一個子串列一定為 2 的冪，因此其 merge tree 為 full binary tree ，所有 leaf 都在最底層。另其長度為 \(2^{k_1}\) ，則 merge tree 的高度為 \(k_1\) 。
當另一個子串列如果也是二的冪，因為第二點中兩者差異不大於 2 倍，因此其大小只可能是 \(2^{k_1-1}\) 或 \(2^{k_1+1}\) 。 merge tree 的高度 \(k_2 = k_1\pm1\)，符合命題。
當第二的子串列不為 2 的冪，那根據假設，此串列的 merge tree 所有 leaf 都在最下面 2 層，而其中一層就是 \(k_1\) ，否則會違反第二點兩者差異不大於兩倍的描述，因此也符合命題。
根據數學歸納法，對第二階段過程中的任意合併，其 merge tree 的所有 leaf 都在最下面 2 層。所以可以得出最後一次合併所產生的 merge tree 也符合命題。
根據論文中所述，可得知 list_sort 中的演算法也是 optimal merge sort。
參見改進 lib/list_sort.c含解說錄影
測試結果:
| Implementation | Elapsed time | Comparisons |
|---|---|---|
| Linux | 170253 | 20573832 |
| shiverssort | 94199 | 14318621 |
| timsort | 95611 | 14906465 |
| Implementation | Elapsed time | Comparisons |
|---|---|---|
| Linux | 298097 | 20621567 |
| shiverssort | 183847 | 14339471 |
| timsort | 203153 | 15254864 |
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe