# 2024q1 Homework2 (quiz1+2)
contributed by < `iLeafy11` >

### timsort

`run_size` 與 `find_run`，利用 `struct list_head` 結構巧妙的節省記憶體空間。

head->next->pre = (struct list_head *) len;

同時，因為 timsort 同時需要利用一個 stack 來儲存 `find_run` 找出來的這些 runs。所以可以利用 `struct list_head *` 的 Doubly Linked List 的特性，將 `find_run` 過後沒有用到的 `prev` 指標拿來作為連結這些 runs 的 head 的 stack list 指標來使用。

TODO: 裡用 `len` 來達到題目敘述的改進方式
>合併序列時，若 run 的數量等於或者略小於 2 的冪，效率會最高；若略大於 2 的冪，效率就會特別低。

我們希望 run 的數量為等於或者略小於 2 冪，這需要考慮 minrun (最小運行長度) 的值的決定。所以我們需要一個類似以下的實作決定 minrun:

int ilog2(int x) return sizeof(int) * 8 - __builtin_clz(x) - 1;

#define minrun_max 64
int minrun(int n)
{
    int a = ilog2(n) + 1;
    int b = a - ilog2(minrun_max);
    int mask = (1 << b) - 1;
    return (n & mask) ? ((n >> b) + 1) : (n >> b);
}

然後可以經過 `find_run` 找出小於 minrun 的 run 對其插入後面的元素並進行 insertion sort，直到該 run 的元素個數等同於 minrun 的數量為止。

不過原先的測驗有以下敘述：
>定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度，若長度太短，就用==二分插入排序==，將 run 後面的元素插入到前面的 run 裡面。

==二分插入排序==的實作。同樣需要用到快慢指標取中點。由於 `find_run` 過程中會將 Doubly Linked List 變成 Singly Linked List，所以所有有關於 sort 的操作皆用 Singly Linked List 的邏輯實作。但是這仍逃不開此處會用 Linked List 進行 Binary Search 的操作！所以由於 Linked List 對於中點的存取並非 random access，時間複雜度並非是 $O(1)$ 而是 $O(N)$！
:::warning
個人認為，依照測驗題敘述，用==二分插入排序==(個人理解為 Binary Insertion Sort)，無法在 Linked List 上發揮優勢，因為在 Linked List 上沒辦法實現:
> Any random element can be accessed in constant time.

所以此處不應該用==二分插入排序==。
:::
:::warning
並且，galloping mode 的實作是基於 Binary Search 才能發揮出優勢，否則比起 Linear Search 會產生更多的比較次數(Comparisons)，所以 galloping mode 在 Linked List 上的 Timsort 就不應該被納入實作的考慮。最起碼應該精進的思考方向不應該是基於一個在 Linked List 資料結構上沒有優勢的"優勢"而去進一步幻想能夠獲得效能或者比較次數的提升。
> reference: https://en.wikipedia.org/wiki/Timsort
:::
### find_nth_bit

https://elixir.bootlin.com/linux/latest/A/ident/find_nth_bit