TimSort：論Java Arrays.sort的穩定性

TimSort 是一種混合的、穩定的排序算法，結合了歸并排序（Merge Sort）和二分插入排序（Binary Insertion Sort）的優點，尤其適用于部分有序的數據。在 Java 中，Arrays.sort() 對對象數組排序時內部使用了 TimSort 算法。

?對于集合的排序實際上也是使用Arrays.sort

如 List.java

    default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator<E> i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}}

類的作用??

主要用于對數組進行高效且穩定的排序。
Java 的 Arrays.sort() 方法在排序對象數組時調用 TimSort。

核心思想??

??識別自然有序子序列（run）??：
遍歷數組，找到已有序的連續子序列。
??擴展短 run??：
若 run 長度小于 MIN_MERGE，使用二分插入排序將其擴展到最小長度。
??合并 run??：
通過歸并操作將所有 run 合并為完全有序的數組。

TimSort 如何實現非遞歸的歸并排序？

傳統的歸并排序通常使用遞歸，將數組不斷對半分割，直到子數組只有一個元素，然后逐層返回并合并。這個過程依賴于程序的調用棧（call stack）來管理子問題。

TimSort 的巧妙之處在于它??用一個自己管理的顯式棧（runBase 和 runLen 數組）替代了遞歸所需的調用棧??。整個過程如下：

??遍歷與壓棧??：一個簡單的循環從左到右遍歷數組，找到或創建小的有序片段（run）。
??管理子問題??：每找到一個 run，就調用 pushRun 將其信息壓入自己的棧中。
??智能合并??：pushRun 之后立即調用 mergeCollapse，根據預設的平衡策略，決定是否要合并棧頂的某些 run。這個合并決策是迭代進行的，而不是遞歸返回時才發生。

通過這種方式，TimSort 將遞歸的“分治”思想轉換成了一個迭代的過程，避免了遞歸深度過大可能導致的 StackOverflowError，并且通過 mergeCollapse 的智能合并策略，進一步優化了歸并的效率。這就是它實現非遞歸歸并排序的原理。

有狀態設計

Arrays.sort沒有創建新實例，而是內部遞歸進行歸并排序的時候創建實例。

有狀態是因為歸并排序需要復制。

這個私有的 TimSort 構造函數主要做了以下幾件重要的事情，本質上都是為了初始化排序過程需要的數據結構和狀態：

保存核心排序參數：
1. this.a = a; ：保存待排序的數組的引用。
2. this.c = c; ：保存用于比較元素順序的比較器 Comparator 。
分配臨時存儲空間 ( tmp 數組) ：
1. TimSort 算法的核心是歸并，在歸并兩個已排序的子序列（稱為 "run"）時，需要一個臨時的存儲空間來存放其中一個子序列。構造函數會預先分配這個名為 tmp 的數組。
2. 為了優化性能和內存使用，它會計算一個合適的初始大小。如果調用者（例如 Arrays.sort ）提供了一個足夠大的工作區數組 ( work )，它會直接使用，避免重復創建數組。
分配用于管理 "run" 的棧 ( runBase 和 runLen 數組) ：
1. TimSort 算法會識別出數組中已經排好序的片段（稱為 "run"），然后將這些 "run" 合并。它使用一個棧來管理這些待合并的 "run"。
2. runBase 數組存儲每個 "run" 的起始索引。
3. runLen 數組存儲每個 "run" 的長度。
4. 構造函數會根據待排序數組的長度 len 計算出一個足夠大但又不過于浪費的棧深度 stackLen ，然后創建這兩個數組。

總而言之， TimSort 的構造函數是一個初始化和準備的過程，它建立了一個包含所有排序所需上下文（待排序數組、比較器、臨時空間、管理棧）的“工作臺”，使得后續的排序步驟可以高效地進行。

關鍵屬性??

屬性名	說明
`MIN_MERGE` (32)	最小 run 長度。短 run 會被擴展至此值，以平衡插入排序和歸并排序的效率。
`MIN_GALLOP` (7)	控制“galloping mode”的閾值，減少連續比較次數。
`INITIAL_TMP_STORAGE_LENGTH` (256)	臨時存儲數組的初始大小，用于歸并操作。
`a`	待排序的數組。
`c`	比較器（若為 `null`，使用自然順序）。
`tmp`	臨時數組，用于歸并操作。
`runBase` 和 `runLen`	存儲 run 的起始位置和長度。`stackSize` 記錄當前棧中 run 的數量。

關鍵方法??

??構造函數??

??TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen)??
- 初始化實例，設置數組和比較器。
- 根據數組長度分配臨時數組 tmp 和 run 信息數組（runBase、runLen）。

??核心方法??

??sort(T[] a, int lo, int hi, Comparator<? super T> c, ...)??
- ??主入口點??：由 Arrays.sort() 調用。
- ??小數組處理??：若長度小于 MIN_MERGE，直接使用二分插入排序。
- ??主循環??：
  1. 調用 countRunAndMakeAscending 識別自然 run。
  2. 若 run 過短，用 binarySort 擴展。
  3. 壓入 run 棧（pushRun）并合并（mergeCollapse）。
- ??最終合并??：循環結束后調用 mergeForceCollapse 完成排序。
??countRunAndMakeAscending??
- 返回自然 run 的長度，并確保其為升序（降序則反轉）。
??binarySort??
- 對小規模數據執行穩定的二分插入排序。
??minRunLength??
- 計算最小 run 長度（介于 MIN_MERGE/2 和 MIN_MERGE 之間）。
??mergeCollapse 和 mergeForceCollapse??
- ??合并規則??：保持棧中 run 長度滿足 runLen[i-2] > runLen[i-1] + runLen[i]。
- 強制合并剩余 run 直到完全有序。
??mergeLo 和 mergeHi??
- 實際歸并操作，根據 run 大小選擇合并方向（低索引或高索引優先）。

與 ComparableTimSort 的關系??

??ComparableTimSort?? 是 TimSort 的變體，專為實現了 Comparable 的對象數組設計，直接調用 compareTo 方法，無需顯式比較器。

總結??

TimSort 通過以下策略實現高效排序：

??動態適應數據特性??：識別自然 run 并智能選擇排序策略。
??平衡合并操作??：通過棧規則避免低效合并。
??混合算法優勢??：結合二分插入排序（小數據）和歸并排序（大數據）的優點。

其設計使其在各類場景下均表現優異，成為 Java 默認排序算法之一。

sort

static <T> void sort(T[] a, int lo, int hi,Comparator<? super T> c, T[] work, int workBase, int workLen)

這個靜態方法是 TimSort 算法的入口。核心思想：

找出數組中已存在的有序片段（稱為 "run"）。
高效合并這些 run。

第一步：處理小數組（Mini-TimSort）

??條件??：待排序元素數量 nRemaining < MIN_MERGE（默認 32）

??countRunAndMakeAscending(a, lo, hi, c)??
- 從數組開頭找到第一個自然有序的 run（升序或降序）。
- 若為降序，通過 reverseRange 反轉為升序。
- 返回 run 的長度 initRunLen。
??binarySort(a, lo, hi, lo + initRunLen, c)??
- 對剩余元素（lo + initRunLen 到 hi）使用二分插入排序。
- 優勢：對小規模且部分有序的數據效率極高。

二分插入排序，二分找到后，直接利用array copy

binary Sort/** The invariants still hold: pivot >= all in [lo, left) and* pivot < all in [left, start), so pivot belongs at left.  Note* that if there are elements equal to pivot, left points to the* first slot after them -- that's why this sort is stable.* Slide elements over to make room for pivot.*/int n = start - left;  // The number of elements to move// Switch is just an optimization for arraycopy in default caseswitch (n) {case 2:  a[left + 2] = a[left + 1];case 1:  a[left + 1] = a[left];break;default: System.arraycopy(a, left, a, left + 1, n);}a[left] = pivot;

第二步：處理大數組（完整 TimSort）

??條件??：數組長度 ≥ MIN_MERGE

??初始化??

new TimSort<>(...)：創建實例，初始化臨時數組 tmp 和 run 棧（runBase/runLen）。

        TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);

??計算最小 run 長度??

minRunLength(nRemaining)：確保 nRemaining / minRun 接近或略小于 2 的冪，使歸并操作均衡。

Timsort 是一種混合排序算法，它通過合并一系列已經排好序的子數組（稱為 "run"）來完成整個數組的排序。為了讓合并過程最高效，理想的情況是每次合并的兩個 run 的長度都差不多。 minRunLength 方法的目的就是計算出一個合適的最小 run 長度（ minRun ），使得原數組可以被分割成數量接近 2的冪的 run。這樣在后續的歸并操作中，可以持續進行大小相近的合并，從而達到最優性能。

int minRun = minRunLength(nRemaining);private static int minRunLength(int n) {assert n >= 0;int r = 0;      // Becomes 1 if any 1 bits are shifted offwhile (n >= MIN_MERGE) {r |= (n & 1);n >>= 1;}return n + r;}

如果 n 不是 k * (2^m) (其中 k 是最終的 n 值，MIN_MERGE=2^5) 這種“干凈”的數， r 就會是 1。

最終返回的是循環結束后的 n 加上標志位 r 。這相當于：如果原始的 n 不能被最終的 n 整除（即存在“余數”，導致 r 為1），那么就把 minRun 的長度加 1。這樣做可以減少 run 的總數，使其更接近 2 的冪。

用一個例子 n = 65 來看看：

初始時 n = 65 , r = 0 。
65 >= 32 ，進入循環。
1. n 是 65 (奇數)， n & 1 是 1。 r |= 1 ，所以 r 變為 1。
2. n >>= 1 ， n 變為 32。
32 >= 32 ，繼續循環。
1. n 是 32 (偶數)， n & 1 是 0。 r |= 0 ， r 仍然是 1。
2. n >>= 1 ， n 變為 16。
16 < 32 ，循環結束。
返回 n + r ，即 16 + 1 = 17 。

所以，對于一個長度為 65 的數組，Timsort 會確保每個 run 的長度至少為 17。這樣 65 / 17 ≈ 3.82 ，數組會被分成 4 個 run。4 是 2 的冪，非常適合歸并。

如果沒有 r ， minRun 就是 16。 65 / 16 = 4 余 1。這會產生 4 個長度為 16 的 run 和 1 個長度為 1 的 run。合并一個長度為 16 和一個長度為 1 的 run 效率就不那么高了。

數學原理說明

注意n < 32是小數組處理的，對于大數組處理minRun的輸入一定是n>=32。

在Java的 TimSort 實現中， MIN_MERGE 的值是32。

這個循環相當于把n分為高5位 q，和剩余位 b，如果b不是0，則會+1

循環結束后 n 的值 q 的范圍是 [16, 31]（高5位就一定是這個范圍，如果n>=32）

當我們把除數從 q 變為 q+1 時，商和余數都會改變。但這個算法的巧妙之處在于，它的目標 ??不是?? 去管理余數的大小，而是 ??確保最終run的總數??（即 ceil(N / minrun) ）非常接近一個2的冪。

我們來做一個更嚴謹的分析：

設數組總長為 N 。設循環右移了 s 次。
我們得到 q = N >> s （即 q = floor(N / 2^s) ）和 r (0或1)。 minrun = q + r 。
我們要分析的run數量是 k = ceil(N / minrun) 。

??情況A??: r = 0
此時 N 的低 s 位全是0， N = q * 2^s 。 minrun = q 。 k = ceil((q * 2^s) / q) = 2^s 。
此時run的數量不多不少，正好是一個2的冪，這是最理想的情況。
??情況B??: r = 1
此時 N 的低 s 位不全為0， N = q * 2^s + rem ，其中 0 < rem < 2^s 。 minrun = q + 1 。
run的數量 k = ceil( (q * 2^s + rem) / (q + 1) ) 。

我們來為這個表達式找一個上下界：
- ??上界??:
  N = q * 2^s + rem < q * 2^s + 2^s = (q+1) * 2^s 。
  所以 N / minrun = N / (q+1) < ((q+1) * 2^s) / (q+1) = 2^s 。
  因為 N / (q+1) 嚴格小于 2^s ，所以 k = ceil(N / (q+1)) 最多是 2^s 。
- ??下界??:
  N = q * 2^s + rem > q * 2^s 。
  所以 N / minrun = N / (q+1) > (q * 2^s) / (q+1) 。
  因此 k = ceil(N / (q+1)) > (q * 2^s) / (q+1) $\approx$ ?(1 - 1/(q+1)) * 2^s 。
結合?q 的范圍是 [16, 31] 。
- 當 q 取最小值16時， q/(q+1) = 16/17 ≈ 0.941 。
- 當 q 取最大值31時， q/(q+1) = 31/32 ≈ 0.969 。
  這意味著 k 的范圍被嚴格限制在 ceil(0.941 * 2^s) 和 2^s 之間。
??舉例??：
- 假設 s=5 ，那么目標run數是 2^5 = 32 。 k 的下界是 ceil(0.941 * 32) = ceil(30.112) = 31 。
  所以，當目標run數是32時，實際的run數 k 只可能是31或32。
- 假設 s=6 ，目標run數是 2^6 = 64 。 k 的下界是 ceil(0.941 * 64) = ceil(60.224) = 61 。
  所以，當目標run數是64時，實際的run數 k 被限制在 [61, 64] 這個極小的范圍內。

該算法通過將 q 限制在 [MIN_MERGE/2, MIN_MERGE-1] 范圍內，并根據余數是否存在來決定 minrun 是 q 還是 q+1 ，最終確保了run的總數 k 要么恰好是一個2的冪 2^s ，要么是在一個非常貼近 2^s 的極小區間內。這為后續歸并操作的平衡性提供了強有力的保證，是Timsort高性能的關鍵之一。

??主循環（`do-while`）??

??a. countRunAndMakeAscending(...)??
同 Mini-TimSort，找到下一個自然 run。
??b. 擴展短 run??
若當前 runLen < minRun，通過 binarySort 強制擴展到 minRun 長度（或剩余元素總數）。
??c. ts.pushRun(lo, runLen)??
將 run 的起始位置和長度壓入棧。
??d. ts.mergeCollapse()??
檢查棧頂 run 是否滿足“棧不變式”（如 runLen[i-2] > runLen[i-1] + runLen[i]）。若不滿足，調用 mergeAt 合并相鄰 run。
??e. 更新索引??
移動 lo 和 nRemaining，準備處理下一個 run。

??最終合并??
- ts.mergeForceCollapse()：合并棧中剩余 run，直到只剩一個 run，完成排序。

子函數總體說明

mergeCollapse() -> mergeAt(n)

??職責??：維持棧的平衡。
??操作??：檢查棧頂 run 長度，若不平衡則計算最佳合并點 n，調用 mergeAt(n)。

mergeAt(i) -> gallopRight(), gallopLeft(), mergeLo(), mergeHi()

??優化 1：跳過有序部分??
- gallopRight：找到 run2 的首元素在 run1 中的插入點，跳過 run1 中已有序部分。
- gallopLeft：找到 run1 的末元素在 run2 中的插入點，跳過 run2 末尾有序部分。
??優化 2：選擇合并策略??
- 根據剩余長度選擇 mergeLo（run1 較短）或 mergeHi（run2 較短），最小化臨時數組使用。

mergeLo() / mergeHi() -> gallopRight(), gallopLeft()

??實際歸并操作??：逐個比較元素并歸并。
??優化 3：Galloping 模式??
- 若一個 run 的元素連續多次“勝出”，進入飛奔模式，調用 gallopRight/gallopLeft 批量移動數據塊。
- minGallop 動態調整進入/退出此模式的閾值。

gallopLeft() / gallopRight()

??飛奔搜索??：
1. 指數級步長（1, 3, 7, 15...）快速定位范圍。
2. 在小范圍內執行二分查找，高效定位插入點。

pushRun(int runBase, int runLen)

這個方法非常直接，它的作用是將一個已經排好序的連續片段（run）的信息記錄下來，存入一個專門的“待合并區”——也就是代碼中的 runBase 和 runLen 數組，它們共同構成了一個棧。

runBase : 記錄這個 run 在原數組中的起始索引。
runLen : 記錄這個 run 的長度。
stackSize : 記錄當前棧中有多少個待合并的 run。

TimSort 的主循環會遍歷整個數組，識別或創建這些小的有序片段（run），然后調用 pushRun 把它們一個個推到這個棧上，等待后續的合并操作。

`mergeCollapse()`

這是 TimSort 算法的精髓所在。每當一個新的 run 被 pushRun 推入棧頂后，mergeCollapse 就會被調用。它的任務是檢查棧頂的幾個 run 是否滿足特定的“平衡”條件（即注釋中提到的兩個不變式）。

??不變式 1??: runLen[i - 2] > runLen[i - 1]
??不變式 2??: runLen[i - 3] > runLen[i - 2] + runLen[i - 1]

這些不變式的核心目標是??保持棧上 run 的長度大致平衡??，避免出現一個非常長的 run 和一個非常短的 run 進行合并，因為那樣效率不高。

mergeCollapse 會持續檢查棧頂的 run，如果不滿足這些條件，它就會選擇相鄰的兩個 run 調用 mergeAt(n) 方法進行合并，直到棧恢復平衡狀態。通過這種方式，它能確保合并操作總是在大小相近的 run 之間進行，從而最大化效率。

    private void mergeCollapse() {while (stackSize > 1) {int n = stackSize - 2;if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] ||n > 1 && runLen[n-2] <= runLen[n] + runLen[n-1]) {if (runLen[n - 1] < runLen[n + 1])n--;} else if (n < 0 || runLen[n] > runLen[n + 1]) {break; // Invariant is established}mergeAt(n);}}

簡單來說，該方法遵循兩條規則（不變量），并持續檢查棧頂的幾個 run 是否滿足這些規則。如果不滿足，就進行合并；如果滿足，就暫時跳過，等待新的 run 加入。

讓我們把棧頂的三個 run （從棧底到棧頂方向）想象成 X, Y, Z。這兩條規則是：

len(X) > len(Y) + len(Z)
len(Y) > len(Z)

當棧上 run 的長度違反了上述任何一條規則時，就需要進行合并。代碼中的 if 語句正是用于檢查這些違規情況：

if?(n?>?0?&&?runLen[n-1]?<=?runLen[n]?+?runLen [n+1]?|| ??n?>?1?&&?runLen[n-2]?<=?runLen[n]?+?runLen[n-1])?{

runLen[n-1] <= runLen[n] + runLen[n+1] 檢查的是規則 1 ( len(X) > len(Y) + len(Z) ) 是否被違反。
runLen[n-2] <= runLen[n] + runLen[n-1] 檢查的是更深一層（W, X, Y）的 run 是否違反了規則 1。
如果以上兩個條件都不成立，代碼會進入 else if 分支。如果此時 runLen[n] <= runLen[n+1] ，則說明規則 2 ( len(Y) > len(Z) ) 被違反，同樣需要合并。

一旦決定合并，算法會優先合并兩個長度較小的相鄰 run ，以維持整體的平衡。這就是 if (runLen[n - 1] < runLen[n + 1]) 這行代碼的作用：

如果 len(X) < len(Z) ，就合并 X 和 Y。
否則，合并 Y 和 Z。

這個合并過程會一直循環，直到棧上所有的 run 都滿足那兩條不變量為止。

什么時候可以跳過（break）？

當棧頂的 run 已經滿足了不變量時，就不需要再進行合并了，可以跳出循環。 else if 中的這個條件負責判斷：

}?else?if?(n?<?0?||?runLen[n]?>?runLen[n?+?1])? { ????break;?//?Invariant?is?established }

這里的 runLen[n] > runLen[n + 1] 正是在檢查規則 2 ( len(Y) > len(Z) )。如果這個條件成立，并且前面更復雜的規則 1 檢查也通過了，就意味著棧目前是“穩定”的，可以暫時停止合并，繼續去數組中尋找下一個 run 。

mergeForceCollapse

循環結束后，最終強制合并，同樣的優化是先合并小的

    private void mergeForceCollapse() {while (stackSize > 1) {int n = stackSize - 2;if (n > 0 && runLen[n - 1] < runLen[n + 1])n--;mergeAt(n);}}

`mergeAt`?

mergeAt 函數之所以實現復雜，是因為它并非簡單的歸并操作，而是 TimSort 這一高效、穩定排序算法的核心優化所在。其復雜性旨在為真實世界中常見的部分有序數據提供極致性能。

TimSort 首先將輸入數組分解為多個已排序的子序列（稱為 "run"）。mergeAt 的任務是將棧上相鄰的兩個 run（例如 run[i] 和 run[i+1]）合并為一個更大的有序 run。

簡單歸并排序會逐個比較元素，而 TimSort 通過智能策略避免對部分有序數據的無效操作。

代碼逐段解析

??準備與棧管理??

private void mergeAt(int i) {int base1 = runBase[i];int len1 = runLen[i];int base2 = runBase[i + 1];int len2 = runLen[i + 1];runLen[i] = len1 + len2;if (i == stackSize - 3) {runBase[i + 1] = runBase[i + 2];runLen[i + 1] = runLen[i + 2];}stackSize--;

獲取兩個 run 的起始位置和長度。
更新棧信息，合并 run 并減少棧大小。

??第一次優化：gallopRight??
```
int k = gallopRight(a[base2], a, base1, len1, 0, c);
assert k >= 0;
base1 += k;
len1 -= k;
if (len1 == 0) return;
```
- 取出 run2 的第一個元素，在 run1 中快速查找其插入位置。
- 通過指數級步長（1, 3, 7, 15...）跳過 run1 中所有小于該元素的區間。
- 跳過部分無需參與后續合并，減少比較次數。
??第二次優化：gallopLeft??
```
len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
assert len2 >= 0;
if (len2 == 0) return;
```
- 取出 run1 的最后一個元素，在 run2 中反向查找插入位置。
- 跳過 run2 中所有大于該元素的區間。
- 精確縮小需合并的范圍。
??第三次優化：選擇 mergeLo 或 mergeHi??
```
if (len1 <= len2)mergeLo(base1, len1, base2, len2);
elsemergeHi(base1, len1, base2, len2);
```
- 根據剩余長度選擇合并策略：
  - mergeLo：當 len1 <= len2 時，復制較短的 run1 到臨時空間。
  - mergeHi：當 len1 > len2 時，復制較短的 run2 到臨時空間。
- 確保臨時空間不超過 N/2，最小化數據拷貝。

gallopLeft 函數的復雜性

結合兩種搜索策略：

??指數搜索（Galloping）??：從 hint 位置以 2^k - 1 步長跳躍，快速定位范圍。
??二分搜索??：在指數搜索確定的范圍內精確查找插入點。
這種“先粗后精”的方式對結構化數據效率遠超純二分搜索。

總結

mergeAt 的復雜性體現了 TimSort 的精髓：

??適應性??：通過 gallop 模式高效處理已有順序的數據。
??效率??：減少無效比較和數據移動，優化內存分配。

正是這些設計使 TimSort 成為 Java、Python 等語言標準庫的默認排序算法。

gallopLeft?

gallopLeft 的核心目標是：
在一個已排序的數組（或數組的一部分）中，快速地為一個給定的 key 找到它應該插入的位置。
如果數組中存在與 key 相等的元素，它會返回 ??最左側?? 那個相等元素對應的索引。
這個特性對于保持排序的穩定性至關重要。

函數簽名

private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint, Comparator<? super T> c
)

參數說明

key：要在數組 a 中查找插入點的元素。
a：進行查找的目標數組。
base：查找范圍在數組 a 中的起始索引。
len：查找范圍的長度。
hint：一個“提示”索引，表示 key 可能的位置。
這是 TimSort 適應性的關鍵，它假設數據具有局部性，即下一個要插入的元素很可能在前一個元素附近。

gallopLeft 的執行過程分為兩個主要階段：
??“飛馳模式”（Galloping）?? 和 ??二分查找（Binary Search）??。

階段一：飛馳模式（指數式搜索）

此階段的目標是利用 hint 快速定位一個包含 key 的較小范圍，而不是從頭開始進行二分查找。

??方向判斷??
首先，比較 key 和 a[base + hint] 的值：
- 如果 c.compare(key, a[base + hint]) > 0，說明 key 在 hint 的右側。此時，算法會向右“飛馳”。
- 如果 key <= a[base + hint]，說明 key 在 hint 的左側或就是 hint 位置的元素。此時，算法向左“飛馳”。
??指數級步進??
算法以指數級增加的步長（1, 3, 7, 15, ...，偏移量由 ofs = (ofs << 1) + 1 計算）進行探測，直到找到一個區間 [lastOfs, ofs]，使得 key 恰好落在這個區間內。
例如，向右飛馳時，直到滿足：
a[base + hint + lastOfs] < key <= a[base + hint + ofs]。
這種方式使得當 key 的實際位置距離 hint 很遠時，也能極快地縮小查找范圍。

階段二：二分查找

??范圍確定??
飛馳階段結束后，已經確定了一個比原始范圍 len 小得多的精確范圍 [lastOfs, ofs]。
??經典二分查找??
在此小范圍內，執行一次標準的二分查找來精確定位插入點：
- 循環條件為 while (lastOfs < ofs)。
- 在查找過程中：
  - 如果 c.compare(key, a[base + m]) > 0，意味著 key 在中間點 m 的右邊，因此將搜索范圍的左邊界更新為 m + 1。
  - 如果 key <= a[base + m]，意味著 key 在 m 的左邊，或者 a[base + m] 就是一個與 key 相等的元素。
    為了找到 ??最左側?? 的插入點，算法會繼續在左半部分查找（ofs = m），而不是立即返回。
    這確保了即使找到一個匹配項，也會繼續向左探索是否還有更早的匹配項。
??返回結果??
最終，lastOfs 和 ofs 會重合，這個重合點就是 key 的最左插入位置。函數返回該偏移量 ofs。

gallopLeft 是 TimSort 算法能夠適應不同數據分布并保持高效的關鍵所在。
它通過 ??“指數搜索 + 二分查找”?? 的兩階段策略，避免了在數據高度有序或存在大段連續區塊時進行逐一比較的低效操作。
通過與 mergeLo 和 mergeHi 的協同工作，它實現了智能的“飛馳模式”，使得 TimSort 在處理真實世界中常見的、部分有序的數據時，性能遠超傳統的歸并排序。

TimSort.mergeLo

TimSort 是一種混合穩定排序算法，結合了歸并排序和插入排序的優點，被應用于 Java 的 Arrays.sort(Object[]) 以及 Python 的 list.sort() 和 sorted() 中。mergeLo 方法是其歸并操作的核心實現之一。

mergeLo 的主要任務是 ??原地、穩定地?? 合并兩個已經排好序且相鄰的子數組（在 TimSort 中稱為 "run"）。

??Lo 的含義??：
這個方法被設計用于 run1 的長度（len1）小于或等于 run2 的長度（len2）的場景。這樣做是為了優化內存使用，因為它總是將 ??較短?? 的 run 復制到臨時空間中，從而最小化額外空間開銷。
??穩定性??：
在合并過程中，如果遇到相等的元素，mergeLo 會優先保留原先排在前面的元素（來自 run1），從而保證了排序的穩定性。

讓我們一步步解析代碼的執行流程：

1) 初始化與數據準備

// ...
T[] a = this.a;          // 減少字段訪問，提升性能
T[] tmp = ensureCapacity(len1); // 確保臨時數組 tmp 有足夠容量
System.arraycopy(a, base1, tmp, cursor1, len1); // 將第一個 run（較短的）完整復制到 tmp 中
// ...

這是 mergeLo 策略的核心：只復制 run1。現在，原數組 a 的 [base1, base1 + len1) 這段空間就可以作為合并后的目標區域了。

2) 處理特殊情況（Degenerate Cases）

// ...
a[dest++] = a[cursor2++]; // 移動 run2 的第一個元素
if (--len2 == 0) { /* ... */ } // 如果 run2 只有一個元素
if (len1 == 1) { /* ... */ }   // 如果 run1 只有一個元素
// ...

代碼首先無條件地將 run2 的第一個元素移動到目標位置。這是一個優化，因為 run2 的第一個元素通常小于 run1 的最后一個元素，可以直接放置。隨后，代碼快速處理了其中一個 run 長度極短（為 1 或 0）的邊界情況，避免進入復雜的主循環。

3) 主合并循環：常規合并與"飛馳模式"的切換

這是函數最精妙的部分。它在一個 while(true) 循環中，根據數據的局部有序性，在兩種模式間自適應切換。

??常規合并階段??：

do {// ...if (c.compare(a[cursor2], tmp[cursor1]) < 0) {a[dest++] = a[cursor2++];count2++; count1 = 0;} else {a[dest++] = tmp[cursor1++];count1++; count2 = 0;}
} while ((count1 | count2) < minGallop);

這個 do-while 循環執行的是標準的"一次比較，一次移動"的歸并操作。
count1 和 count2 記錄了每個 run 連續獲勝（即其元素被選中）的次數。
當任何一個 run 連續獲勝的次數達到 minGallop 閾值時，循環退出，算法認為數據出現了高度的局部有序性，適合切換到更高效的模式。
??飛馳模式 (Galloping Mode)??：

do {// ...count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);// ... 批量復制 ...count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);// ... 批量復制 ...
} while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);

??目的??：
當一個 run 的元素持續小于另一個 run 時，逐個比較就顯得低效。飛馳模式通過一種類似二分查找的方式（gallopLeft / gallopRight），快速跳過另一個 run 中一長段連續的元素。
??過程??：
例如，gallopRight(a[cursor2], tmp, ...) 會在 tmp（run1）中快速查找有多少個元素小于 a[cursor2]。然后通過 System.arraycopy 將這些元素進行 ??批量復制??，極大地提升了效率。
??模式切換??：
這種模式會一直持續，直到兩個 run 的批量復制長度（count1 和 count2）都小于 MIN_GALLOP，表明數據的有序性不再明顯，此時會退回到常規合并模式。

4) 收尾工作

// ...
if (len1 == 1) { /* ... */ }       // run1 還剩一個元素
else if (len1 == 0) { throw new IllegalArgumentException(...); }
else { System.arraycopy(tmp, cursor1, a, dest, len1); } // run2 已耗盡，復制 run1 剩余部分

循環結束后，必然有一個 run 已經被完全合并。這部分代碼負責將另一個 run 中剩余的所有元素復制到目標數組的末尾。

算法精髓——自適應性

TimSort 的強大之處在于其自適應性，這在 mergeLo 中通過 minGallop 變量體現得淋漓盡致：

??進入飛馳模式??：
當數據有序性高時（一個 run 連續獲勝），count 迅速達到 minGallop，進入飛馳模式以加速處理。
??懲罰與獎勵??：
- minGallop--：在飛馳模式中，每次成功的 gallop 都會讓 minGallop 減 1，使得下一次更容易保持在飛馳模式。
- minGallop += 2：如果飛馳模式效果不佳并退出，minGallop 會加 2，使得下次進入飛馳模式的門檻變高，避免在隨機性強的數據上浪費時間。

這種機制使得 TimSort 能夠動態適應輸入數據，無論數據是接近有序還是完全隨機，都能提供接近最優的性能。

總結

TimSort 是高度優化的穩定混合排序算法，融合以下技術：

??基本框架??：歸并排序。
??小數組/短 run 處理??：二分插入排序（binarySort）。
??歸并策略??：通過棧不變式（mergeCollapse）實現智能合并。
??性能加速??：飛奔模式（gallopLeft/gallopRight）適應部分有序數據。

??優勢??：對真實世界數據（高度有序或完全隨機）均表現卓越。

TimSort 和 DualPivotQuicksort 對比

TimSort 和 DualPivotQuicksort 是兩種不同的排序算法，應用在不同的場景下。除了分別用于對象和基本類型數組外，它們的主要差別在于算法核心、穩定性、性能和空間復雜度。

實際上DualPivotQuicksort實現有更多技巧，見：

深入淺出 Arrays.sort（DualPivotQuicksort）：如何結合快排、歸并、堆排序和插入排序

核心算法邏輯

??DualPivotQuicksort (雙軸快速排序):??

是對經典快速排序算法的改進：
- 傳統快速排序選擇一個“軸點”（pivot），將數組分為兩部分（小于軸點的和大于軸點的）。
- 雙軸快速排序選擇兩個軸點，將數組分為三部分：小于第一個軸點的、在兩個軸點之間的、大于第二個軸點的，然后遞歸排序。
優勢：
- 比單軸快速排序性能更好，能更好地處理數據分布，減少遞歸深度。
- 對于非常小的數組，會切換到插入排序（Insertion Sort）以提高效率。

??TimSort:??

是一種混合（Hybrid）排序算法，結合了歸并排序（Merge Sort）和插入排序（Insertion Sort）的優點：
- 首先在數據中尋找已排好序的連續子序列（稱為“自然運行”）。
- 如果 run 太短，使用二分插入排序（Binary Insertion Sort）擴展。
- 合并這些 runs（類似歸并排序），通過維護 run 的棧并遵循特定規則來平衡合并成本。
設計目標：在真實世界數據（通常包含部分有序片段）上表現優異。

TimSort 是一種混合穩定的排序算法，它結合了歸并排序和插入排序。當合并兩個已經有序的run時，算法需要逐個比較來自兩個run的元素，以決定下一個元素應該放誰，從而保證合并后的序列仍然有序且穩定。這個過程是順序的、有狀態的，后一步的決策依賴于前一步的結果。因此，很難將單個合并操作分解到多個線程中去并行處理而不產生巨大的同步開銷。

哪個“更好”取決于評判標準和應用場景：

對于大規模、隨機的數據集，在多核CPU上， DualPivotQuicksort 通常更快。因為它可以利用多核優勢進行并行計算，這是它被選為Java基本類型數組（如 int[] , double[] ）默認排序算法的原因。
對于部分有序的數據， TimSort 通常表現更好。 TimSort 被設計用來利用數據中已經存在的順序，在這種情況下，它的比較次數遠少于 n log n ，性能非常出色。現實世界中的很多數據都具有這種部分有序的特征。
當需要穩定排序時，必須使用 TimSort 。穩定排序保證了相等元素的原始相對順序在排序后不會改變。 DualPivotQuicksort 是不穩定的，而 TimSort 是穩定的。因此，Java中對象數組（ Object[] ）的 Arrays.sort() 和 Collections.sort() 都使用 TimSort 。

總結對比表

特性	DualPivotQuicksort	TimSort
??核心算法??	雙軸快速排序	混合歸并排序和插入排序
??穩定性??	? 不穩定	?? 穩定
??最壞時間復雜度??	O(n2)	O(n log n)
??平均時間復雜度??	O(n log n)	O(n log n)
??最好時間復雜度??	O(n log n)	O(n)
??空間復雜度??	O(log n)	O(n)
??JDK 用途??	`Arrays.sort`（基本類型）	`Arrays.sort`/`Collections.sort`（對象）