# 2019q3 Homework4 (quiz4)
contributed by < `davinais` >
###### tags: `sysprog` `sysprog2019`

## 題目

考慮一個單向 linked list:

typedef struct __list {
    int data;
    struct __list *next;
} list;

在不存在環狀結構的狀況下，以下函式能夠對 linked list 元素從小到大排序:

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    LL0;

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                LL1;
            } else {
                LL2;
                merge = merge->next;
            }
            LL3;
        } else {
            if (!merge) {
                LL4;
            } else {
                LL5;
                merge = merge->next;
            }
            LL6;
        }
    }
    return start;
}

==解析==

從上下文的程式碼，以及程式碼中 `merge` 變數，應該可以猜測這是在做 merge sort。

那麼想必然，一開始一定就是要將 list 給斷開了。LL0 的部分，由於我們才剛指派 `left` 以及 `right` ，不太可能再重新對其指派值；而且這是排序，不太可能會跳過元素，因為不會是 C 和 D。而考慮到斷開 list 成為兩部分，由於如果從 `right->next` 斷開的話，等同於後面的 list 也全部都被斷開，因此不可能是此選項。最合理的還擇即是從 `left->next` 斷開，這樣 list 就會斷成 `left`：只有一個頭元素 以及 `right`：剩下的 list 兩部分。

接下來進入了 recursive 的部分，由於 left 的部分只有一個元素因此會直接結束 right 的部分會讓這個 list 一個一個斷開目前的 head，直到 right 的部分只剩下一個為止。

再來進入迴圈，我們先以呼叫堆疊最上層，也就是 left 跟 right 都只有一個元素的情況為例：

一開始先將 merge 設為 NULL ，並以 left 或 right 至少其一非空作為迴圈持續條件。

每個 iteration 以 right 是否為空或 right 與 left 皆非空且 right 的資料大於 left 為條件，若為真，則代表 left 要先被放入 list 中以維持遞增的排序。反之，則就代表 right 要先被放進 list 中。

假設剛才的條件為真，代表我們要將 left 先放進 list 中。我們會再檢查 merge 是否為空以確定是否為初始情況，如果 merge 為空即代表這是第一次執行迴圈，我們需要設定 merge。那麼要不要設定 start 呢？考慮到這個 sort 函數最後是回傳 start，start 必定是已排序 list 的 head。既然這是迴圈初次執行的情況，我們當然要將 list 的最開頭設為 start。於是 LL1 自然要選擇 `start = merge = left`。
那麼如果 merge 不為空，那我們就直接插入到 merge 的後面，因此 LL2 選擇 `merge->next = left` 。

我們將目前的 `left` 放進去了，那麼接下來就是要讓 `left` 的下一個跟 `right` 互相比較了，於是 LL3 選擇 `left = left->next`。

如果先前的條件不為真，那麼代表我們要將 right 先放入 list 中，與先前的情況類似，因此選項也相對：於是 LL4 選擇 `start = merge =right`， LL5 選擇 `merge->next->right` ，LL6 選擇 `right = right->next` 。

我們接下來繼續跑完這個程式，由於我們已經切到剩下 `left` 與 `right` 兩個單獨元素了，跑完這個迴圈，我們會得到一個排序好的 list head `start` ，裡面有兩個元素。接下來回到上一個 stack ，依此類推，我們每次都將只有單一元素的 `left` 與排好的 list `right` 進行 merge，最後我們就會得到一個排序好的 list 了。

不過這個方法其實是一個非常沒有效率的 merge sort 實作方法，**基本上根本就是 insertion sort 了**，還有很大的改善空間。

### 改善空間

單純就不限定資料類型的排序，Merge sort 要達到最佳時間複雜度 $O(n \log n)$ 的話，至少我們應該要對半拆分才行，如此一來在 merge 時的大小比較平衡。

並且再考慮 recursive 版本的 Merge Sort，在資料量不多的情況下，由於還存在呼叫堆疊的 overhead ，可能還不會比 iterative 版本的 insertion sort 還快，於是我們可以考慮以下的 Sorting 方案，先選定某一 k 值，並且原則上先使用 Merge Sort 做排序，而直到我們拆到剩下 k 個以下的元素時，使用 Insertion Sort 作為排序，應該能夠比我們直接使用 Merge Sort 還快速。

:::warning
TODO: 探索 [introsort](https://en.wikipedia.org/wiki/Introsort) 和 [timsort](https://en.wikipedia.org/wiki/Timsort) 原理，思考同樣手法用於上述程式的機會
:notes: jserv
:::

::: success
補上 Timsort
:::

#### Timsort

而 Timsort 也是一個透過組合 Merge sort 與 Insertion sort 的解決方案，設計者考慮到真實世界當中通常有自然升序或者是降序的部分，因此我們試著找出這種 partially sorted 的部分(我們在此稱之為 run )，再運用 insertion sort 將其至少補成足夠 merge 的長度之後(稱為 minrun )，再以 merge sort 的方式完成整個排序。

選取 run 的大小是非常重要的，良好的 minrun 大小可以控制合併次數在 2 的冪數或者是比其稍微小一點的數字。以 $2112$ 個元素為例，如果我們選擇 $32$ 作為 minrun，我們需要做 66 次合併，那麼我們會有完美的 64 次再額外加上 2 次合併，造成合併大小相差過大，會有效能問題。但如果我們選擇 $33$ ，那麼我們只需要剛好的 64 次就可以完成了。

首先，考慮到 insertion sort 的效率，如果我們需要額外的 sorting 來補長 run 到 minrun，勢必 minrun 不能選得太大，以免效能降低。在此我們選擇 minrun 為 $64$ 。我們直接取 list 長度的前 6 個有效 bit (32~63)，

{%gist Davinais/38e008c96b26211102691074f700b27e %}

:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 指出程式改進空間，特別是考慮到 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort);
3. 將上述 singly-linked list 擴充為 circular doubly-linked list 並重新實作對應的 `sort`;
4. 依循 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 程式碼的方式，改寫上述排序程式;
5. 嘗試將原本遞迴的程式改寫為 iterative 版本;
6. 將 [2019q1 第 3 週測驗題 (下)](https://hackmd.io/@sysprog/SkrVSKiU4) 提及的 XOR linked list 列入考量，也實作對應的排序程式，並比較效能和記憶體開銷;
7. 比照 [List Sort](https://arxiv.org/pdf/1310.7890.pdf) 的手法來分析前述程式 (含擴充版本) 的效能表現;
:::

---