# 2025q1 Homework1 (lab0)
contributed by < `kdnvt` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 126
Model name: Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
Stepping: 5
CPU MHz: 1200.000
CPU max MHz: 3600.0000
CPU min MHz: 400.0000
BogoMIPS: 2380.80
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 128 KiB
L2 cache: 2 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 針對佇列操作的程式碼實作
### q_free
一開始的程式為以下
```c
void q_free(struct list_head *l)
{
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
if (entry->value)
free(entry->value);
free(entry);
}
free(l);
return;
}
```
但當我完成 insert , remove 等程式，發現有關 malloc failure on new 的測試有時會發生錯誤，而且是 segmentation fault 。我決定用 `make valgrind` 來檢查出錯的地方，於是有了以下訊息：
```
# Test of malloc failure on new
==26221== Invalid read of size 8
==26221== at 0x10E6C9: q_free (queue.c:45)
==26221== by 0x10ADC4: queue_quit (qtest.c:838)
==26221== by 0x10D54E: do_quit (console.c:253)
==26221== by 0x10DF9F: finish_cmd (console.c:593)
==26221== by 0x10C728: main (qtest.c:963)
==26221== Address 0x8 is not stack'd, malloc'd or (recently) free'd
```
根據以上訊息，可以知道問題發生在 ```q_free``` 中，而 ```q_free``` 中第一個遇到的就是 ```list_for_each_entry_safe``` 這個巨集，於是我去看 ```list.h``` 中此巨集的實作方法：
```c
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
```
可以看到這個巨集一開始就直接用
>entry = list_entry((head)->next, __typeof__(*entry), member)
將 `list_entry` 的內容指派給 `entry` 。而且也直接使用`(head)->next` ，所以我很快發現我忘記檢查傳入的引數是否為 `NULL` 或 empty queue，於是我將程式碼改成以下：
```diff
void q_free(struct list_head *l)
{
+ if (!l)
+ return;
+ if (list_empty(l)) {
+ free(l);
+ return;
+ }
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
if (entry->value)
```
#### 其他想法：
上面那段程式中
```c
if (!l)
return;
if (list_empty(l)) {
free(l);
return;
}
```
有點冗長，於是我嘗試將程式碼改成以下：
```c
if (!l || (list_empty(l) && (free(l),true)))
return;
```
其中用到了 || 及 && 在前者條件已經確定下，後者不會被執行的技巧。而後面的 ``(free(l),true)`` 則是我參閱規格書中 comma operator ：
> The left operand of a comma operator is evaluated as a void expression; there is a sequence point after its evaluation. Then the right operand is evaluated; the result has its type and value. 97) If an attempt is made to modify the result of a comma operator or to access it after the next sequence point, the behavior is undefined.
因此我想它的行為應該會是執行完前面的 `free(l)` 後直接以 true 來取代這段 expression 。
最後發現根本不用這麼麻煩，因為如果傳入 free 的指標本身就指向 NULL ，free 是不會有任何行為的，所以根本不用多做一個檢查。
簡化後的版本：
```diff
void q_free(struct list_head *l)
{
- if (!l)
- return;
- if (list_empty(l)) {
+ if (!l || list_empty(l)) {
free(l);
return;
}
element_t *entry, *safe;
- list_for_each_entry_safe (entry, safe, l, list) {
- if (entry->value)
- free(entry->value);
- free(entry);
- }
+ list_for_each_entry_safe (entry, safe, l, list)
+ q_release_element(entry);
free(l);
return;
```
### q_sort
一開始決定以<s>疊代</s> **迭代**的方式實作 merge sort 。
:::warning
依據《[國家教育研究院雙語詞彙、學術名詞暨辭書資訊網](https://terms.naer.edu.tw/)》，"iterative" 一詞翻譯為「迭代」。
注意「[疊](https://dict.revised.moe.edu.tw/dictView.jsp?ID=2195)」和「[迭](https://dict.revised.moe.edu.tw/dictView.jsp?ID=2169)」語意不同:
* 疊: 堆聚、累積
* 迭: 輪流、更替，如：「更迭」。《詩經．邶風．柏風》：「日居月諸，胡迭而微。」
依本處情境來，乃逐一節點走訪，存取特定的記憶體內容，因此該用「迭」
:notes: jserv
:::
初始版本：
```c
＃define STACKSIZE 100000
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int count = 0, n = q_size(head);
struct list_head *sorted[STACKSIZE];
struct list_head *cur, *safe;
list_for_each_safe (cur, safe, head)
INIT_LIST_HEAD(sorted[count++] = cur);
for (int size_each_list = 1; size_each_list < n; size_each_list *= 2) {
for (int i = 0; i + size_each_list < n; i += size_each_list * 2) {
struct list_head *left = sorted[i];
struct list_head *right = sorted[i + size_each_list];
sorted[i] = merge(left, right);
}
}
list_add_tail(head, sorted[0]);
}
/*
* The list in this function is doubly circular linked_list without
* the Head node.
* Move each node in list right to list left at corresponding position.
*/
struct list_head *merge(struct list_head *left, struct list_head *right)
{
struct list_head *head = left;
if (strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) > 0)
list_move_tail(head = (right = right->next)->prev, left);
struct list_head *tail = head->prev;
while (left != tail && right->next != left) {
int cmp = strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value);
if (cmp <= 0) // to keep sorting stable, split condition as <= , >
left = left->next;
else
list_move_tail((right = right->next)->prev, left);
}
while (right->next != left && right->next != head) {
int cmp = strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value);
list_move_tail((right = right->next)->prev, cmp < 0 ? head : left);
// Shoud be cmp <= 0 because of stability
}
return head;
}
```
上面的 `merge` 的實作本來是想把右列的 sorted list 一個一個判斷後插入左列，但越寫越不直覺，還要想一些例外狀況，可讀性差也不易理解，於是寫完之後決定重寫一份：
```diff
struct list_head *merge(struct list_head *left, struct list_head *right)
{
- struct list_head *head = left;
-
- if (strcmp(list_entry(left, element_t, list)->value,
- list_entry(right, element_t, list)->value) > 0)
- list_move_tail(head = (right = right->next)->prev, left);
-
- struct list_head *tail = head->prev;
- while (left != tail && right->next != left) {
- int cmp = strcmp(list_entry(left, element_t, list)->value,
- list_entry(right, element_t, list)->value);
- if (cmp <= 0) // to keep sorting stable, split condition as <= , >
- left = left->next;
- else
- list_move_tail((right = right->next)->prev, left);
- }
- while (right->next != left && right->next != head) {
- int cmp = strcmp(list_entry(left, element_t, list)->value,
- list_entry(right, element_t, list)->value);
+ struct list_head *head;
+
+ int cmp = strcmp(list_entry(left, element_t, list)->value,
+ list_entry(right, element_t, list)->value);
+ struct list_head **chosen =
+ cmp <= 0 ? &left : &right; // cmp <= 0 for stability
+ head = *chosen;
+ *chosen = (*chosen)->next;
+
+ list_del_init(head);
- list_move_tail((right = right->next)->prev, cmp < 0 ? head : left);
- // Shoud be cmp <= 0 because of stability
+ while (left->next != head && right->next != head) {
+ cmp = strcmp(list_entry(left, element_t, list)->value,
+ list_entry(right, element_t, list)->value);
+ chosen = cmp <= 0 ? &left : &right; // cmp <= 0 for stability
+ list_move_tail((*chosen = (*chosen)->next)->prev, head);
}
+ struct list_head *remain = left->next != head ? left : right;
+ struct list_head *tail = head->prev;
+
+ head->prev = remain->prev;
+ head->prev->next = head;
+ remain->prev = tail;
+ remain->prev->next = remain;
+
return head;
}
```
上面這段程式碼是先判斷找出 `value` 最小的 element 當成第一個 node ，然後比較左右列最小的 node 一個一個插入進去。
執行起來較為對稱，也沒有太多例外狀況，較好理解可讀性也較佳。
需要特別注意的是為了保持排序的穩定性，條件為 `cmp <= 0` 而不是 `cmp < 0` 。
不過 `q_sort` 中有一個致命的缺點，就是陣列 sorted 是固定長度，若佇列太小會很浪費空間，太大則會無法執行。另外，這次作業似乎禁止在 `q_sort` 中使用 `malloc` ，不過就算能用，對於記憶體也可能會是很大的負擔。於是我想了另一套實作方法來解決這個問題：
```diff
@@ -3,19 +3,34 @@ void q_sort(struct list_head *head)
if (!head || list_empty(head) || list_is_singular(head))
return;
- int count = 0, n = q_size(head);
- struct list_head *sorted[STACKSIZE];
-
struct list_head *cur, *safe;
list_for_each_safe (cur, safe, head)
- INIT_LIST_HEAD(sorted[count++] = cur);
+ cur->prev = cur;
+
+ /* pointer first points to first sorted list */
+ struct list_head *first = head->next;
+ INIT_LIST_HEAD(head);
+ while (first->prev->next != head) {
+ struct list_head **last = &first;
+ struct list_head *next_list = (*last)->prev->next;
+ struct list_head *next_next_list = next_list->prev->next;
+
+ while ((*last) != head && next_list != head) {
+ /* Make each sorted list doubly circular list
+ * to make use of function merge.
+ */
+ (*last)->prev->next = (*last);
+ next_list->prev->next = next_list;
+ (*last) = merge((*last), next_list);
- for (int size_each_list = 1; size_each_list < n; size_each_list *= 2) {
- for (int i = 0; i + size_each_list < n; i += size_each_list * 2) {
- struct list_head *left = sorted[i];
- struct list_head *right = sorted[i + size_each_list];
- sorted[i] = merge(left, right);
+ /* The result of function merge is a doubly circular list,
+ * so make tail of list point it next to next sorted list.
+ */
+ last = &((*last)->prev->next);
+ *last = next_next_list;
+ next_list = (*last)->prev->next;
+ next_next_list = next_list->prev->next;
}
}
- list_add_tail(head, sorted[0]);
+ list_add_tail(head, first);
}
```
這個方法主要使用每個 sorted list 尾端節點的 `next` 指向下一個 sorted list ，如此一來我就可以用 linked_list 來走訪各個子 sorted list ，不需要額外的空間來記錄這些 sorted list 的位置。
結構大致上如下：
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
e [label="{<ref2> | first }"];
a [label="{ <ref1> | <data> 1 | <ref2> }"]
b [label="{ <ref1> | <data> 5 | <ref2> }"];
c [label="{ <ref1> | <data> 7 | <ref2> }"];
f [label="{ <ref1> | <data> 2 | <ref2> }"]
g [label="{ <ref1> | <data> 3 | <ref2> }"];
h [label="{ <ref1> | <data> 6 | <ref2> }"];
d [label="{ <ref1> | head | <ref2> }"];
a:data:n -> e:ref2:c [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
c:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> f:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:data:s -> f:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
f:ref2:c -> g:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref2:c -> h:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref1:c -> g:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref1:c -> f:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
圖中 1 5 7 為一個 sorted list ， 2 3 6 為另一個 sorted list ，以一個 `first` 來記錄整個 linked list 的位置，最後一個節點則指向 `head` ，而 head 指向自己。
==註：此圖僅為說明，若是圖中的佇列，以程式碼執行的結果應該不會出現三個三個一組的情形。==
範例說明：
假如一個佇列順序為 1 6 7 2 5 3 。
程式一開始先以
```c
struct list_head *cur, *safe;
list_for_each_safe (cur, safe, head)
cur->prev = cur;
/* pointer first points to first sorted list */
struct list_head *first = head->next;
INIT_LIST_HEAD(head);
```
將佇列切割成單個 sorted list ，圖如下：
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
e [label="{<ref2> | first }"];
a [label="{ <ref1> | <data> 1 | <ref2> }"]
b [label="{ <ref1> | <data> 6 | <ref2> }"];
c [label="{ <ref1> | <data> 7 | <ref2> }"];
f [label="{ <ref1> | <data> 2 | <ref2> }"]
g [label="{ <ref1> | <data> 5 | <ref2> }"];
h [label="{ <ref1> | <data> 3 | <ref2> }"];
d [label="{ <ref1> | head | <ref2> }"];
a:data:n -> e:ref2:c [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> f:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
f:data:s -> f:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
f:ref2:c -> g:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref2:c -> h:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref1:c -> h:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref1:c -> g:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
接著對每兩個相鄰的 sorted list 做合併：
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
e [label="{<ref2> | first }"];
a [label="{ <ref1> | <data> 1 | <ref2> }"]
b [label="{ <ref1> | <data> 6 | <ref2> }"];
c [label="{ <ref1> | <data> 2 | <ref2> }"];
f [label="{ <ref1> | <data> 7 | <ref2> }"]
g [label="{ <ref1> | <data> 3 | <ref2> }"];
h [label="{ <ref1> | <data> 5 | <ref2> }"];
d [label="{ <ref1> | head | <ref2> }"];
a:data:n -> e:ref2:c [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
b:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> f:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:s -> f:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:data:s -> f:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
f:ref2:c -> g:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref2:c -> h:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref1:c -> g:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref1:s -> h:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
e [label="{<ref2> | first }"];
a [label="{ <ref1> | <data> 1 | <ref2> }"]
b [label="{ <ref1> | <data> 2 | <ref2> }"];
c [label="{ <ref1> | <data> 6 | <ref2> }"];
f [label="{ <ref1> | <data> 7 | <ref2> }"]
g [label="{ <ref1> | <data> 3 | <ref2> }"];
h [label="{ <ref1> | <data> 5 | <ref2> }"];
d [label="{ <ref1> | head | <ref2> }"];
a:data:n -> e:ref2:c [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
f:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> f:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:data:s -> f:ref1:c [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
f:ref2:c -> g:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref2:c -> h:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref1:c -> g:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref1:s -> h:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
e [label="{<ref2> | first }"];
a [label="{ <ref1> | <data> 1 | <ref2> }"]
b [label="{ <ref1> | <data> 2 | <ref2> }"];
c [label="{ <ref1> | <data> 3 | <ref2> }"];
f [label="{ <ref1> | <data> 5 | <ref2> }"]
g [label="{ <ref1> | <data> 6 | <ref2> }"];
h [label="{ <ref1> | <data> 7 | <ref2> }"];
d [label="{ <ref1> | head | <ref2> }"];
a:data:n -> e:ref2:c [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
h:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> f:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:data:s -> f:ref1:c [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
f:ref2:c -> g:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref2:c -> h:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
h:ref1:c -> g:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
g:ref1:c -> f:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
最後再將 `head` 插回排序好的佇列中，再回傳就完成了。
## 研讀 lib/list_sort.c
除了程式碼及註解外，我參考 [DokiDokiPB](https://hackmd.io/@DokiDokiPB/SJfES914O#list_sort)，才發現 commit message 也是很重要的資訊來源。如果實作上較為複雜或有其他考量，開發者會把重要的資訊及考量的點也寫在 commit message 中。
>延伸閱讀：
>[lib/list_sort: optimize number of calls to comparison function](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09?branch=b5c56e0cdd62979dd538e5363b06be5bdf735a09&diff=split)
研讀 `lib/list_sort.c` 時我發現 `list_sort.c` 實作方法跟我的有一些相似之處，例如用 `prev` 來串起排序好的子串列，以及用 bottom up 的方法實作排序。不過也有許多不同的地方， `list_sort.c` 在合併的過程中，直接把子串列當成單向鏈結串列，因此操作上省去了許多 `prev` 的指標操作，只要在最後一次 merge 時再串起即可。
而選取合併的子串列時，雖然是用 bottom up 的方法，但不同於一般的 level order merge ——即每一層相同大小的子串列都合併完後，才合併更大的子串列—— `list_sort.c` 的實作上採用了 depth-first order ，目的是為了避免 thrashing 。
level order merge 在每一層都會幾乎讀取所有子串列(有些實作上最後一條子串列可能不對讀到)，當要排序的雙向鏈結串列超過 L1 cache 的大小，同一層前面排序好的子串列必須從 cache 中搬出，讓給後面要排序的子串列。而到了下一層，剛被搬出的子串列又要被搬進 cache ，造成資料不斷被搬進搬出 cache ，頻繁讀取卻沒有利用到 cache ，對於效能是很大的傷害。如果採用 depth-first order，就可以趁相近的子串列都還在 L1 cache 時，盡量將大小相同的兩者合併，進而打造出 cache friendly 的實作方法。
不過只用 depth-first order 還有一個很大的問題，就是會造成 unbalanced merge ，即兩個大小差異極大的子串列做合併。（我的實作中沒有考慮到這一點，這是一個可以再改進的部份。）
因此，這份 commit ：[lib/list_sort: optimize number of calls to comparison function](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09?branch=b5c56e0cdd62979dd538e5363b06be5bdf735a09&diff=split) 的作者 George Spelvin 提出了另一種實作方式來改善這個缺點。
首先，他分析了不同實作下所需的 compares 次數。
$n\times \log_{2}(n) - K \times n + O(1)$
其中使用一般 Top down merge sort 因為可以將子串列平均分割，因此平均情況下 K = 1.248 ，而一般的 bottom up merge sort 平均情況下 K = 0.965 。（George Spelvin 做的實驗顯示 K = 1.01）
但是使用 Top down merge sort 或其他改良版的 merge sort (如佇列merge sort)時，都會用到 breadth-first multi-pass structure ，與我們想要以 depth-first order 善用 cache 的需求不符。
George Spelvin 透過確保每次合併時，兩個子串列的大小不會大於 $2 : 1$ ，成功的將 K 值增加到 1.207，省下了 $0.2 \times n$ 次的 compares 操作。
> George Spelvin 在 commit message 最後附上了一些分析合併排序的論文：
>
>[Bottom-up Mergesort: A Detailed Analysis](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5260)
>Wolfgang Panny, Helmut Prodinger Algorithmica 14(4):340--354, October 1995
>
>[The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.5380)
>Wei-Mei Chen, Hsien-Kuei Hwang, Gen-Huey Chen Journal of Algorithms 30(2); Pages 423--448, February 1999
>
>[Queue-Mergesort](https://doi.org/10.1016/0020-0190(93)90088-q)
>Mordecai J. Golin, Robert Sedgewick
Information Processing Letters, 48(5):253--259, 10 December 1993
### 確保 2 : 1 的實作方法
這段操作十分精簡且高效，。
George Spelvin 甚至在 commit message 的最後寫上了：
> I confess to being more than a little bit proud of how clean this code turned out. It took a lot of thinking, but the resultant inner loop is very simple and efficient.
先引入一個變數 `count` 來記錄目前讀進的元素個數，並根據其 bit pattern 來判斷每次的合併。
節錄 `list_sort.c` 中的註解：
```c
/*
* The number of pending lists of size 2^k is determined by the
* state of bit k of "count" plus two extra pieces of information:
*
* - The state of bit k-1 (when k == 0, consider bit -1 always set), and
* - Whether the higher-order bits are zero or non-zero (i.e.
* is count >= 2^(k+1)).
*
* There are six states we distinguish. "x" represents some arbitrary
* bits, and "y" represents some arbitrary non-zero bits:
* 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
* 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* (merge and loop back to state 2)
*/
```
其中
```c
/* k k-1
* v v
* 0: 0 0 x: 0 pending of size 2^k; x pending of sizes < 2^k
* 1: 0 1 x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 2: x 1 0 x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 3: x 1 1 x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 4: y 0 0 x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 5: y 0 1 x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* (merge and loop back to state 2)
*/
```
左邊的 0/1 代表第 k 個 bit ，右邊的 0/1 代表第 k-1 個 bit 。
一開始不知道那一個才是 bit k ，看了好久才看懂。
x 最多為 k-2 bits ，因此最大為 $2^{k-1}-1$ 。
對於第 k bit ，可以將其分為以下六種狀態，並由其所在的狀態來判斷目前長度為 $2^k$ 的串列數量：
`0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k`
代表目前有 x 數量個元素在長度小於 $2^k$ 的子串列中。
`1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k`
代表有 ($2^{k-1}$ + x) 個元素在長度小於 $2^k$ 的子串列中。
`2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k`
代表有 ($2^k$ + x) 個元素在長度小於 $2^k$ 的子串列中，但為了確保之後的合併不會超過 2 : 1 ，因此不會將那 $2^k$ 個合併成一個長度為 $2^k$ 的串列。
`3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k`
代表有一個長度為 $2^k$ 的串列，另外有 ($2^k$ + x) 個元素在長度小於 $2^k$ 的子串列中。
因為至少有 $2^k$ + $2^{k-1}$ 個元素，所以可以將那 $2^k$ 個元素合併。如果之後都沒有其他元素了，剩下長度差異最多也就是 $2^k : 2^{k-1}=2:1$ 。
`4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k`
代表有一個長度為 $2^k$ 的串列，另外有 ($2^k$ + x) 個元素在長度小於 $2^k$ 的子串列中。跟狀態 2 一樣，雖然有可合併成 $2^k$ 的子串列，但不會立即合併成 $2^k$。
`5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k`
代表有兩個長度為 $2^k$ 的串列，另外有 ($2^{k-1}$ + x) 個元素在長度小於 $2^k$ 的子串列中。兩個長度為 $2^k$ 的子串列一樣不會立即合併成 $2^{k+1}$ ，唯有確定後面的元素個數達到 $2^k$ ，足以確保差距不會超過 $2^{k+1}:2^k =2:1$ ，才會進行合併並且回到狀態 2 。
> 參考 [DokiDokiPB](https://hackmd.io/@DokiDokiPB/SJfES914O#list_sort) 及[hankluo6](https://hackmd.io/@hankluo6/2021q1quiz2#%E8%AA%AA%E6%98%8E-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-liblist_sortc-%E6%9C%80%E4%BD%B3%E5%8C%96%E6%89%8B%E6%B3%95)
|count decimal|count binary|merge|before merge|after merge
| -------- | -------- | -------- |---|---|
0|0000 |No| NULL| X
1|0001 |No| 1 |X
2|0010 |Yes| 1-1 |2
3|0011 |No| 1-2 |X
4|0100 |Yes| 1-1-2 |2-2
5|0101 |Yes| 1-2-2 |1-4
6|0110 |Yes| 1-1-4 |2-4
7|0111 |No| 1-2-4 |X
8|1000 |Yes| 1-1-2-4 |2-2-4
9|1001 |Yes| 1-2-2-4 |1-4-4
10|1010 |Yes | 1-1-4-4| 2-4-4
11|1011 |Yes | 1-2-4-4| 1-2-8
12|1100 |Yes| 1-1-2-8| 2-2-8
13|1101 |Yes | 1-2-2-8 |1-4-8
14|1110|Yes | 1-1-4-8 |2-4-8
15|1111 |No | 1-2-4-8 |X
16|10000 |Yes| 1-1-2-4-8| 2-2-4-8
有了以上的初步理解，就可以來看 list_sort.c 程式實作：
```c
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);
```
先分析每一次讀取時 `count` 的變化，有可能是：
$0\overbrace{11..11}^\text{k 個} = 01x$ (狀態 1)
這樣的話會被下面的程式排除，不給合併。
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
/*....*/
}
```
另一種則是
$y0\overbrace{11..11}^\text{k 個} = y01x$ (狀態 5)
每一次 `count` + 1 ，都會有一個 bit k 從 0 進位成 1 ，這個 bit 為 least signifcant clear bit 。而這個 bit 處於狀態 5 ，也就是目前有兩個長度為 $2^k$ 的子串列。
在它之前的所有 bits 皆為狀態 3 。
$x111..11 = x11x$ (狀態 3)
包括第 0 個 bit
> The state of bit k-1 (when k == 0, consider bit -1 always set)
根據狀態 3 的敘述，可以說目前 $\forall \ i \in Z, 0\le i\le k-1$ 都有剛好一條長度為 $2^i$ 的子串列。
也就是目前的子串列大小排列是：
$\overset{pending}{\implies}\overbrace{2^0\overset{prev}{\implies}2^1\overset{prev}{\implies}.....\overset{prev}{\implies}2^k}^\text{k 個 prev}\overset{prev}{\implies}2^k\overset{prev}{\implies}..$
目前在長度小於 $2^k$ 的子串列中的元素個數為：
$(2^0 + 2^1 + 2^2 + ... + 2^{k-1}) + 1 = (2^k - 1)+1 = 2^k$
數學式中最後的 $1$ 並不在各個子串列中，他是這個迴圈的結尾才會被加進的元素。這個數學式讓我們得知這個迴圈結束時長度小於 $2^k$ 的子串列中的元素個數已經到了 $2^k$ ，因此可以合併兩條大小為 $2^k$ 的子串列。
所以在一開始的迴圈只要往前 k 次就可以到達要合併子串列：
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
到達後進行合併：
```c
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;
}
```
然後輸入下一個元素：
```c
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
沒有待輸入的元素時，將剩餘的子串列從小到大合併：
```c
/* 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;
}
```
最後在用 `merge_final` 合併最後兩條子串列，並串起 `prev` ：
```c
merge_final(priv, cmp, head, pending, list);
```
用這種方式就可以達成 depth-first merge sort 同時保證兩者差異不會大於 $2:1$ 。
### 一些證明
前提：所有子串列其長度皆為 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 中串列大小的比例差距限制是二比一
因為目的是為了避免合併差距過大，因此使用二比一而不是更大三比一、四比一很合理。需要考慮的是為什麼不用三比二或四比三這種比例。
先簡述一下 list_sort 的演算法：
第一階段：
將節點一個一個讀取，如果確定合併的大小不會超過整體的特定比例，就將之前的串列合併。因為本質還是 bottom up merge sort ，所以此階段的合併都是同大小，所有子串列也都會是二的冪。
第二階段：
當所有節點都讀進並盡可能的同大小合併後，就來到必須合併不同大小的階段。這個階段會將子串列由小大到一個接一個合併。
從以上兩階段可以看出，因為第一階段都是二的冪，在維持 $2m : 2m+1$ 比例的情況下，第一階段結束時最大的子串列就是 $2^{\lfloor log_22mn/{(2m+1)} \rfloor}$ 。
在第二篇論文 [The cost distribution of queue-mergesort, optimal mergesorts, and
power-of-two rules](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.5380) 中看到以下這段話：
>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$ 的二的冪會有兩個，再不包括的情況下卻又會不存在。如果是寫成
$n/3 < 2^{\lfloor log_22n/3 \rfloor} \leq 2n/3$
就符合這段話的描述。
而這段敘述講述了一件事， $2^{\lfloor log_22n/3 \rfloor}$ 可以找到最接近 $n/2$ 的二的冪。
如果今天是用 $2^{\lfloor log_23n/5 \rfloor}$ 去求 $2^k$ ，則當 $n = 13$ 時，$2^{\lfloor log_23n/5 \rfloor} = 4$，而最接近 $13/2$ 的二的冪卻是 $8$ 。
這代表如果在第一階段用 $3:2$ 的比例去限制，在第二階段合併中，最後一次合併會是 $9:4$ ，這個比例差距已經超過第一階段的 $3:2$ ，而同樣的反例在 $2m:2m+1 ,m>2$ 中也都會發生。因此這樣的演算法只能用在 $2:1$ 的情況。
### 證明 list_sort 的演算法是 optimal mergesort
optimal merge sort 定義：在最差的情況下，比較次數小於等於所有其他 mergesort 。
對所有 mergesort ，都可以繪製出一個 merge tree 來表示其合併的順序及長度，每一個節點的權重代表當下的串列長度。方形的是 external node (leaf) ，圓形的是 internal node 。如下圖所示：
```graphviz
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 };
}
```
> 參考資訊: [graphviz](https://stackoverflow.com/questions/41194837/how-to-get-graphviz-dot-to-represent-binary-tree-correctly)
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](https://www.sciencedirect.com/science/article/pii/002001909390088Q?via%3Dihub) 中以下段落：
>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 都在最下面兩層。**
**證明過程：**
第一階段所有合併皆為二的冪，符合命題。
**用數學歸納法證明第二階段：**
最小端的子串列只可能是 (1,1) 或 (1,2)，兩者合併都符合命題。
對第二階段過程中的任意合併，假設其兩個子串列都符合命題。
則合併的過程中，由第一點可知，其中一個子串列一定為二的冪，因此其 merge tree 為 full binary tree ，所有 leaf 都在最底層。另其長度為 $2^{k_1}$ ，則 merge tree 的高度為 $k_1$ 。
當另一個子串列如果也是二的冪，因為第二點中兩者差異不大於兩倍，因此其大小只可能是 $2^{k_1-1}$ 或 $2^{k_1+1}$ 。 merge tree 的高度 $k_2 = k_1\pm1$，符合命題。
當第二的子串列不為二的冪，那根據假設，此串列的 merge tree 所有 leaf 都在最下面兩層，而其中一層就是 $k_1$ ，否則會違反第二點兩者差異不大於兩倍的描述，因此也符合命題。
根據數學歸納法，對第二階段過程中的任意合併，其 merge tree 的所有 leaf 都在最下面兩層。所以可以得出最後一次合併所產生的 merge tree 也符合命題。
根據論文中所述，可得知 list_sort 中的演算法也是 optimal merge sort 。
Sign in with Wallet
Connect another wallet