2023q1 Homework4 (quiz4)

contributed by < gaberplaysgame >

測驗 1

---

測驗 2

Timsort 為合併了插入排序與合併排序的混合排序演算法，在排序開始前會把資料分為一個又一個的 Run (區塊)，針對每個 Run 的大小來去決定要利用插入排序或合併排序。一般而言長度小於64的小區塊使用插入排序，大於的則使用合併排序。

Run 在 Timsort 中為已經排序（遞增）的區塊，若是所遇到的區塊為遞減的形式，則會強制將區塊反轉轉為遞增形式，這點可以在下方程式碼窺見：

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);
    }

另 Timsort 有參數 MIN_RUN 規範 Run 的最小值，長度在 16~64 不等，用於判斷使用哪種方式來去做排序。若 run_len < MIN_RUN，使用插入排序，反之則使用合併排序。此外根據 Run 遞增/遞減的特性，若是一個區塊長度已經到達 MIN_RUN 指定值，但下一個數字仍為遞增/遞減的排序，該 Run 的長度會跟著增加。

---

測驗 3