---
tags: linux kernel class
---

# 2023q1 Homework4 (quiz4)
contributed by < `willwillhi1` >

## 測驗 `2`
`Timsort` 是 **Insertion Sort** 和 **Merge Sort** 的結合，特點是速度快．在最佳狀況只有 $O(n)$，平均和最糟狀況也有 $O(n log (n))$。

整個做法的原理是先把資料分成小區塊(又可以叫做 `run`)，一般來說範圍會在 `32 ~ 64` 之間，然後把小區塊用 `insertion sort` 排序，再把這些區塊用 `merge sort` 合併起來。
參考 [Wikipedia: Timsort](https://en.wikipedia.org/wiki/Timsort)
> Timsort was designed to take advantage of runs of consecutive ordered elements that already exist in most real-world data

，如果陣列是由多個部分排序的數列所組成表現較好，但是如果在 `random array` 表現會較差，因為 `insertion sort` 在有排序的數列上是 `best case`。

/* random array */
timsort: 171.0 us
qsort: 103.0 us

#### Insertion sort
* 在 `next_partition` 裡執行，每次先從 `first` 開始往後找有排序的數列。覺得原本程式會違反 `stable` 的特性(?，因為 `reverse` 的實作是頭尾兩兩交換。
* 原本的實作如下，但是考慮到這個例子 [5, 4~1~, 4~2~ , 4~3~, 3, 6]，此時要做 `reverse` 前，`first` 指向 `5`，`next` 指向 `6`，做了 `reverse` 後會變成 [3, 4~3~, 4~2~ , 4~1~, 5, 6]。

if (cmp(cur, next)) {
    while (next < last && cmp(cur, next)) {
        ++run_len;
        cur += size;
        next += size;
    }
} else {
    while (next < last && !cmp(cur, next)) {
        ++run_len;
        cur += size;
        next += size;
    }
    __reverse(first, next, size);
}

* 然後判斷找到的數列長度是大於或小於 `MIN_RUN`，如果不到 `MIN_RUN` 個代表這個大小適合用插入排序法，就往後取到 `MIN_RUN` 個後做 `__insertion_sort`。

last = first + MIN_RUN * size < last ? first + MIN_RUN * size : last;

#### Merge 規則
* 為了達到 `balanced merge`，`timsort` 會依照以下的規則來判斷是否要執行合併，`run_length` 回傳該 `run` 長度。

run_length(stack[top]) > run_length(stack[top - 1])
run_length(stack[top]) + run_length(stack[top - 1]) > run_length(stack[top - 2])

* `Timsort` 是 `stable` 排序演算法，所以在 `merge` 時只能找相鄰的 `run` 合併。
#### Minimum run size
> merging is most efficient when the number of runs is equal to, or slightly less than, a power of two

如果陣列是完全隨機的，在 `merge` 時會希望可以平衡，也就是分成略小於等於 2 的冪個 `run`，這麼一來可以避免需要合併兩個大小相差很大的 `run`。
以下說明如何計算出適當的 `Minimum run size` 來讓 `run` 符合條件。
計算 `Minimum run size`:
目的是要讓整個陣列依照 `min run size` 被分成略小於或等於二的冪個。
一般來說 `run_size` 會在 `32 ~ 64` 之間，
整體的演算法是取整個陣列長度的前 6 位，之後再加上剩餘的部分的 `1` 的個數即可。

假設 array size = 2156 = 0b100001101100
取前六位 = 0b100001 = 33
再加上剩餘的 set bits: 0b101100，總共 3 bits
所以 min run size = 33 + 3 = 36
2156/36 = 59，略小於 64

#### Merge
* 一般的 `linear merge`，需要用到額外的記憶體。
* `__inplace_merge`:
* Merge two runs: `[1, 2, 3, 6, 10]` and `[4, 5, 7, 9, 12, 14, 17]`
* 將 `cur1` 指向大於 `first2` 的第一個數，接著將 `cur2` 指向大於 `cur1` 的第一個數

    while (cur_1 < last_2 && cmp(cur_2, cur_1) >= 0)
        cur_1 += size;

    while (cur_2 < last_2 && cmp(cur_2, cur_1) < 0)
        cur_2 += size;

* `__reverse(start, end, size)` 的效果是把 `start` 到 `end-1` 的數字反轉
* ` __reverse(cur_1, first_2, size)`
* `__reverse(first_2, cur_2, size);`


* 最後再反轉 `cur1 ~ cur2`
* `__reverse(cur_1, cur_2, size);`

* 這麼一來就排完 `first1 ~ cur1` + `first2 ~ cur2 的兩個數列`，所以新的
* `first_1 = cur_1 + (cur_2 - first_2)`
* `first_2 = cur_2`
* 接下來以此類推持續下去，直到 `cur1 == last2` 或 `cur_1 > first_2`。
* 值得一提的是，再找 `cur1` 和 `cur2` 的位置時，原本的程式是用 `linear search`。

    while (cur_1 < last_2 && cmp(cur_2, cur_1) >= 0)
        cur_1 += size;

    while (cur_2 < last_2 && cmp(cur_2, cur_1) < 0)
        cur_2 += size;

* 但因為是在一個已排序的陣列找所以可以用 `binary search` 來加速，不過在 [Wikipedia: timsort](https://en.wikipedia.org/wiki/Timsort) 裡有提到是用另一個演算法 `expotential search` 來找的。
* expotential search 簡單介紹 :
* 與 `binary search` 最主要的差異在於不是直接選擇陣列中間的元素來比較，而是依序去比較索引為 2^i^ 的元素，`i` 從 `0` 開始，可以分為以下情況
1. 如果要查找的元素比索引為 2^i^ 的元素大，就繼續往下一個索引 2^i+1^ 比對。
2. 如果比索引為 2^i^ 的元素小，就可以用二分搜尋法在 2^i-1^+1 ~ 2^i^-1 的範圍內找我們要找的元素。

#### 參考資料
* [Wikipedia: timsort](https://en.wikipedia.org/wiki/Timsort)