# Timsoert 筆記

## tim_sort運作原理
Timsort 致力於從以下三個方面，改進合併排序演算法：

1. 加快合併（merge）過程
2. 減少進行合併的次數。
3. 在某些特定情況下，尋找比合併排序更有效的排序方法
---

1. 識別出資料中已排序的子序列 (這些子序列稱為 run)。

若 run 的數量等於或者略小於 2 的冪，效率會最高；若略大於 2 的冪，效率就會特別低。
* 控制每個 run 的長度，定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度，若長度太短，就用二分插入排序，將 run 後面的元素插入到前面的 run 裡面。
* 選擇 minrun 的策略是 Timsort 的關鍵，其中一個實務上的方法是，取資料長度 N 的前 6 位，若剩餘位中任何一位被設置，則加 1。這主要是為了在處理隨機數列時，使得 N 能夠被 minrun 切分成 2 的冪的 run，以便在合併時達到最佳平衡。

minrun 的設計目的是讓剩餘資料在分割為 minrun 時，能夠盡可能接近 2 的冪，從而使得後續的合併過程更高效；實際操作中，會不斷將 n 除以 2，直到 n 小於一個預設的最小合併長度（MIN_MERGE），過程中只要有任何一次不能整除 2，最終結果就加一，這種方法確保分組接近 2 的冪。

例子：當 N = 2112，將 2112 化成二進位是 0b100001000000取前六位: 0b100001 –> 33剩餘的 bit 沒有被設置的，所以 33 就是預期的 minrun。

2. 判斷何時需要合併這些 run。

Timsort 採用一組堆疊 (stack) 來暫存 run，此舉是為了避免在一開始就掃描整個資料範圍來產生 run，從而降低記憶體開銷。過程中，Timsort 運用 merge_collapse 函式來確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：

1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。

當不符合這些條件時，函式會決定是否進行合併。例如，考慮 3 段 run: A 的長度為 30，B 的長度為 20，C 的長度為 10，由於 A 的長度不大於 B 加 C 的總和（亦即 $A <= B + C$ ），且 C 的長度小於 A，因此會選擇將 C 與 B 進行合併，形成兩個新的 run

* A: 30
* BC: 30。

藉此，不僅確保堆疊中 run 的長度平衡，且因合併只能在相鄰的兩個 run 間進行，以確保排序的穩定性，因此合併操作僅可能採取 A+(B+C) 或 (A+B)+C 的形式進行。此舉讓 Timsort 在執行時兼顧高效又穩定。

3. 透過不斷合併這些 run 來達成全資料範圍的排序。

處理兩個相鄰子數列的合併過程中，直接在記憶體中操作會遇到一定的挑戰，因為大量的記憶體操作不僅實作困難，且效率也未必理想。因此，Timsort 採取了使用一塊臨時記憶區的策略，其大小設定為兩個子數列（A、B）中較短者的長度。

合併的方式又可分為：
* 逐對合併(one-pair-at-a-time)
* 當 A 的長度小於 B 時，會先將 A 數列暫存。直觀的合併方法是從 A 和 B 的開頭開始進行逐對比較，將較小的元素放置於 A 的原位置，這一過程一直持續到 A 和 B 完全排序，類似於經典的合併排序。

* Galloping mode
* 考慮到 A 和 B 都是已排序好的數列，我們可持續改進：首先尋找 B 的首個元素（即 $B_0$）在 A 中的排序位置，從而確定 A 中有一段是小於 $B_0$ 者，可將這部分元素放回 A。接著，尋找剩餘 A 的首個元素在 B 中的位置，如此反覆進行，直到完成排序(搜尋方法會使用 [galloping search](https://rust-algo.club/searching/exponential_search/))。

Galloping mode 在多數情況效果顯著，但對於隨機資料序列而言，採用 galloping search 可能會比 linear search 慢，因此在timsort 內有一個變數叫做 min_gallop，初始值為 MIN_GALLOP，存放要切換到 Galloping 模式前，要有幾次輸出 Buffer 資料連續來同一個 run 的次數。每次 Galloping 模式離開時會讓 min_gallop 加 1，但是若 min_gallop 一直持續運作時，每運作一回合，則會讓 min_gallop 減 1。

作者列出 galloping search 對比 linear search 的計算花費，可以看到在 i=7 之前 galloping search 會需要更多的比較次數，而比較是很花計算資源的，所以 MIN_GALLOP預設是 7，即當比較 7 次後，若都來自同一個 Run ，則切換到 Galloping 模式。

**示意圖**

綠色：未排序、紅色：進入堆疊等待排序。
紫色：將被插入前一個 run 的節點、橘色：完成排序。

首先給定一個鍊結串列如下，Minrun 為 3。

digraph _graph_name_ {
    label = "Minrun = 3";
    rankdir=LR; # 順序由左至右(上下是"TD")
    graph [fontname="DFKai-SB"]; # 此三行是設定字型
    node [fontname="DFKai-SB"];  # 中文務必指定
    edge [fontname="DFKai-SB"];  # 不然可能會出現亂碼
    {rank = same stack stack_box}
    {rank = same head A}
    head[shape=plaintext,fontcolor = red]
    A[label = "3", style=filled, fillcolor = green]
    B[label = "4", style=filled, fillcolor = green]
    C[label = "1", style=filled, fillcolor = green]
    D[label = "10", style=filled, fillcolor = green]
    E[label = "8", style=filled, fillcolor = green]
    F[label = "5", style=filled, fillcolor = green]
    G[label = "0", style=filled, fillcolor = green]
    H[label = "2", style=filled, fillcolor = green]
    I[label = "6", style=filled, fillcolor = green]
    J[label = "7", style=filled, fillcolor = green]
    K[label = "9", style=filled, fillcolor = green]
    stack[shape=plaintext,fontcolor = blue]
    stack_box[shape = s, label = "NULL"]
    
    # 這邊是 edge (邊)
    stack->stack_box
    stack->head [style=invis]
    head->A->B->C->D->E->F->G->H->I->J->K
}

先找 run，不足 Minrun = 3，故使用 insertion sort 將下個節點加入當前的 run 當中。

digraph _graph_name_ {
    label = "Minrun = 3";
    rankdir=LR; # 順序由左至右(上下是"TD")
    graph [fontname="DFKai-SB"]; # 此三行是設定字型
    node [fontname="DFKai-SB"];  # 中文務必指定
    edge [fontname="DFKai-SB"];  # 不然可能會出現亂碼
    {rank = same stack stack_box}
    {rank = same head A}
    head[shape=plaintext,fontcolor = red]
    A[label = "3", style=filled, fillcolor = red]
    B[label = "4", style=filled, fillcolor = red]
    C[label = "1", style=filled, fillcolor = purple]
    D[label = "10", style=filled, fillcolor = green]
    E[label = "8", style=filled, fillcolor = green]
    F[label = "5", style=filled, fillcolor = green]
    G[label = "0", style=filled, fillcolor = green]
    H[label = "2", style=filled, fillcolor = green]
    I[label = "6", style=filled, fillcolor = green]
    J[label = "7", style=filled, fillcolor = green]
    K[label = "9", style=filled, fillcolor = green]
    stack[shape=plaintext,fontcolor = blue]
    stack_box[shape = s, label = "NULL"]
    
    # 這邊是 edge (邊)
    stack->stack_box
    stack->head [style=invis]
    head->A->B->C->D->E->F->G->H->I->J->K
}

加入堆疊準備排序。

digraph _graph_name_ {
    label = "Minrun = 3";
    rankdir=LR; # 順序由左至右(上下是"TD")
    graph [fontname="DFKai-SB"]; # 此三行是設定字型
    node [fontname="DFKai-SB"];  # 中文務必指定
    edge [fontname="DFKai-SB"];  # 不然可能會出現亂碼
    {rank = same stack stack_box}
    {rank = same head C}
    head[shape=plaintext,fontcolor = red]
    A[label = "3", style=filled, fillcolor = red]
    B[label = "4", style=filled, fillcolor = red]
    C[label = "1", style=filled, fillcolor = red]
    D[label = "10", style=filled, fillcolor = green]
    E[label = "8", style=filled, fillcolor = green]
    F[label = "5", style=filled, fillcolor = green]
    G[label = "0", style=filled, fillcolor = green]
    H[label = "2", style=filled, fillcolor = green]
    I[label = "6", style=filled, fillcolor = green]
    J[label = "7", style=filled, fillcolor = green]
    K[label = "9", style=filled, fillcolor = green]
    stack[shape=plaintext,fontcolor = blue]
    stack_box[shape = s, label = "run[0] len=3"]
    
    # 這邊是 edge (邊)
    stack->stack_box
    stack->head [style=invis]
    head->C->A->B->D->E->F->G->H->I->J->K
}

完成該 run 的排序。

digraph _graph_name_ {
    label = "Minrun = 3";
    rankdir=LR; # 順序由左至右(上下是"TD")
    graph [fontname="DFKai-SB"]; # 此三行是設定字型
    node [fontname="DFKai-SB"];  # 中文務必指定
    edge [fontname="DFKai-SB"];  # 不然可能會出現亂碼
    {rank = same stack stack_box}
    {rank = same head C}
    head[shape=plaintext,fontcolor = red]
    A[label = "3", style=filled, fillcolor = orange]
    B[label = "4", style=filled, fillcolor = orange]
    C[label = "1", style=filled, fillcolor = orange]
    D[label = "10", style=filled, fillcolor = red]
    E[label = "8", style=filled, fillcolor = red]
    F[label = "5", style=filled, fillcolor = red]
    G[label = "0", style=filled, fillcolor = red]
    H[label = "2", style=filled, fillcolor = green]
    I[label = "6", style=filled, fillcolor = green]
    J[label = "7", style=filled, fillcolor = green]
    K[label = "9", style=filled, fillcolor = green]
    stack[shape=plaintext,fontcolor = blue]
    stack_box[shape = s, label = "run[0] len=3"]
    
    # 這邊是 edge (邊)
    stack->stack_box
    stack->head [style=invis]
    head->C->A->B->D->E->F->G->H->I->J->K
}

尋找下個 run，下個 run = 4，但是順序相反，因此使用 reverse 將它排列成正確的順序，並加入堆疊等待排序。

digraph _graph_name_ {
    label = "Minrun = 3";
    rankdir=LR; # 順序由左至右(上下是"TD")
    graph [fontname="DFKai-SB"]; # 此三行是設定字型
    node [fontname="DFKai-SB"];  # 中文務必指定
    edge [fontname="DFKai-SB"];  # 不然可能會出現亂碼
    {rank = same stack stack_box}
    {rank = same head C}
    head[shape=plaintext,fontcolor = red]
    A[label = "3", style=filled, fillcolor = orange]
    B[label = "4", style=filled, fillcolor = orange]
    C[label = "1", style=filled, fillcolor = orange]
    D[label = "0", style=filled, fillcolor = red]
    E[label = "5", style=filled, fillcolor = red]
    F[label = "8", style=filled, fillcolor = red]
    G[label = "10", style=filled, fillcolor = red]
    H[label = "2", style=filled, fillcolor = green]
    I[label = "6", style=filled, fillcolor = green]
    J[label = "7", style=filled, fillcolor = green]
    K[label = "9", style=filled, fillcolor = green]
    stack[shape=plaintext,fontcolor = blue]
    stack_box[shape = s, label = "run[1] len=4\nrun[0] len=3"]
    
    # 這邊是 edge (邊)
    stack->stack_box
    stack->head [style=invis]
    head->C->A->B->D->E->F->G->H->I->J->K
}

並且因為 run[0] 的長度小於 run[1] 的長度，不符合前面提到的 B 的長度要大於 C 的長度，因此將 run[0] 和 run[1] 合併。

digraph _graph_name_ {
    label = "Minrun = 3";
    rankdir=LR; # 順序由左至右(上下是"TD")
    graph [fontname="DFKai-SB"]; # 此三行是設定字型
    node [fontname="DFKai-SB"];  # 中文務必指定
    edge [fontname="DFKai-SB"];  # 不然可能會出現亂碼
    {rank = same stack stack_box}
    {rank = same head C}
    head[shape=plaintext,fontcolor = red]
    A[label = "1", style=filled, fillcolor = orange]
    B[label = "3", style=filled, fillcolor = orange]
    C[label = "0", style=filled, fillcolor = orange]
    D[label = "4", style=filled, fillcolor = orange]
    E[label = "5", style=filled, fillcolor = orange]
    F[label = "8", style=filled, fillcolor = orange]
    G[label = "10", style=filled, fillcolor = orange]
    H[label = "2", style=filled, fillcolor = green]
    I[label = "6", style=filled, fillcolor = green]
    J[label = "7", style=filled, fillcolor = green]
    K[label = "9", style=filled, fillcolor = green]
    stack[shape=plaintext,fontcolor = blue]
    stack_box[shape = s, label = "run[0] len=7"]
    
    # 這邊是 edge (邊)
    stack->stack_box
    stack->head [style=invis]
    head->C->A->B->D->E->F->G->H->I->J->K
}

尋找下一個 run，並且因為它已經排序完成，直接加入堆疊。

digraph _graph_name_ {
    label = "Minrun = 3";
    rankdir=LR; # 順序由左至右(上下是"TD")
    graph [fontname="DFKai-SB"]; # 此三行是設定字型
    node [fontname="DFKai-SB"];  # 中文務必指定
    edge [fontname="DFKai-SB"];  # 不然可能會出現亂碼
    {rank = same stack stack_box}
    {rank = same head C}
    head[shape=plaintext,fontcolor = red]
    A[label = "1", style=filled, fillcolor = orange]
    B[label = "3", style=filled, fillcolor = orange]
    C[label = "0", style=filled, fillcolor = orange]
    D[label = "4", style=filled, fillcolor = orange]
    E[label = "5", style=filled, fillcolor = orange]
    F[label = "8", style=filled, fillcolor = orange]
    G[label = "10", style=filled, fillcolor = orange]
    H[label = "2", style=filled, fillcolor = red]
    I[label = "6", style=filled, fillcolor = red]
    J[label = "7", style=filled, fillcolor = red]
    K[label = "9", style=filled, fillcolor = red]
    stack[shape=plaintext,fontcolor = blue]
    stack_box[shape = s, label = "run[1] len=4\nrun[0] len=7"]
    
    # 這邊是 edge (邊)
    stack->stack_box
    stack->head [style=invis]
    head->C->A->B->D->E->F->G->H->I->J->K
}

到達鍊結串列的尾端，將堆疊 pop 出來進行合併。

digraph _graph_name_ {
    label = "Minrun = 3";
    rankdir=LR; # 順序由左至右(上下是"TD")
    graph [fontname="DFKai-SB"]; # 此三行是設定字型
    node [fontname="DFKai-SB"];  # 中文務必指定
    edge [fontname="DFKai-SB"];  # 不然可能會出現亂碼
    {rank = same stack stack_box}
    {rank = same head C}
    head[shape=plaintext,fontcolor = red]
    A[label = "1", style=filled, fillcolor = orange]
    B[label = "2", style=filled, fillcolor = orange]
    C[label = "0", style=filled, fillcolor = orange]
    D[label = "3", style=filled, fillcolor = orange]
    E[label = "4", style=filled, fillcolor = orange]
    F[label = "5", style=filled, fillcolor = orange]
    G[label = "6", style=filled, fillcolor = orange]
    H[label = "7", style=filled, fillcolor = orange]
    I[label = "8", style=filled, fillcolor = orange]
    J[label = "9", style=filled, fillcolor = orange]
    K[label = "10", style=filled, fillcolor = orange]
    stack[shape=plaintext,fontcolor = blue]
    stack_box[shape = s, label = "run[0] len=11"]
    
    # 這邊是 edge (邊)
    stack->stack_box
    stack->head [style=invis]
    head->C->A->B->D->E->F->G->H->I->J->K
}

## Timsort 相較於合併排序的改善
1. 改善比較次數
在尚未排序的序列中，已經排序好的子序列會被加入到同一個 runs 之中，以減低額外排序的開銷。這個特性使得 Timsort 在處理具有部分有序性質的序列時表現更好。
2. 插入排序優化
Timsort 中的一個關鍵改進是對小規模子陣列採用插入排序。相比之下，Mergesort 在處理小規模陣列時仍然使用歸併操作。插入排序對於小規模陣列的排序效率更高，這使得 Timsort 在實際應用中具有更好的性能。
3. Cache Miss 改善
相比於傳統遞迴版本的 Mergesort 採用廣度優先的合併順序，Timsort 類似於 Linux 核心 Mergesort 的作法採用深度優先的合併順序。這樣做的好處是，趁元素才剛存取過仍在快取時，就進行合併，從而降低 cache miss 的機率。

digraph _graph_name_ {
    # 基本宣告
    rankdir=LR; # 順序由左至右(上下是"TD")
    node [shape=record, fontname=Helvetica, fontsize=10]
    
    A[label = "1", style=filled, fillcolor = aquamarine1]
    B[label = "2", style=filled, fillcolor = aquamarine1]
    C[label = "8", style=filled, fillcolor = aquamarine1]
    D[label = "4", style=filled, fillcolor = aquamarine1]
    E[label = "3", style=filled, fillcolor = coral1]
    F[label = "5", style=filled, fillcolor = chartreuse1]
    G[label = "7", style=filled, fillcolor = chartreuse1]


    # list_head 的 next
    A->B->C->D->E->F->G

}

## 參考資料
[timsort.txt](https://svn.python.org/projects/python/trunk/Objects/listsort.txt)

[V8 內的排序演算法 — Timsort](https://yuanchieh.page/posts/2019/2019-08-09-v8-%E5%85%A7%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort/)

[排序算法 (六) - Timsort](https://www.sakuratears.top/blog/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%EF%BC%88%E5%85%AD%EF%BC%89-TimSort.html)

[世界上最快的排序算法——Timsort](https://www.cnblogs.com/sunshuyi/p/12680918.html)

[指數搜尋 Exponential Search](https://rust-algo.club/searching/exponential_search/)