# 2019q3 Homework4 (quiz4)
contributed by < `Ting199708` >

:::warning
注意上方格式，特別是空白
:::

## 第一題

### 題目

:::info
考慮一個單向 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;
}

:::

==分析與想法==

此程式的目標為排序一 linked list

* 首先觀察程式，我們可以發現若缺少了 LL0 ，將會導致無窮遞迴的情況，為了壁面這種情況， LL0 需為 ==left->next = NULL== ，另外 `left = sort(left)` 及 `right = sort(right)` 這兩行遞迴的程式可以讓 list 中 ***最右邊*** 的兩個數值先行比較並排列。

* 再來看到 for 迴圈內的 if 條件式，在兩筆新數值首次進入時，我們發現若 left->data < right->data 則不需更改兩者的順序，因此 LL1 為 ==start = merge = left== ，其中， merge 的功用為在下一次進入迴圈內將數值接續。 另外，因為 `left` 已排序完成，我們可以將其設為 `left->next` ，此動作將在 LL3 實現，因此 LL3 為 ==left = left->next==

* 同理，若 left->data > right->data ，我們會進入 else 中，如同小於時的處理方式， LL4 為 ==start = merge = right== ， LL6 為 ==right = right->next==

* 接下來，透過帶入測值觀察程式， LL2 及 LL5 的功用為將兩者中數值較小的排至 start->next ，因此 LL2 為 ==merge->next = left== ， LL5 為 ==merge->next = right==

因此，完整程式碼如下：

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

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

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

:::warning
這個實作的缺陷呢？
:notes: jserv
:::

## 延伸題目

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

1. 如上
2.