TimSort 深度剖析：對歸併排序的優化策略與 Java 核心源碼實現解讀

背景：為什麼需要 TimSort？

經典歸併排序對**逆序數據**性能退化至 O(n²)。TimSort（Python/Java/Android 默認排序算法）針對**真實世界數據常含有序片段**的特點，通過**自然分區**與**智能歸併策略**實現：

• 最佳情況（完全有序）：O(n)
• 平均/最壞情況：O(n log n)
• 穩定排序，空間 O(n)

核心優化思想

1. 自然分區： 掃描一次數組，將**嚴格遞增**的 run 直接作為分區；**嚴格遞減**的 run 反轉後作為分區。保證分區內有序且穩定。
2. 最小分區長度： MIN_MERGE = 32。分區過小時用二分插入排序擴充至 minRun（根據數組長度計算，2的冪附近）。
3. 歸併棧與合併規則： 維護待歸併分區棧，滿足不變量：

   runLen[i-3] > runLen[i-2] + runLen[i-1]   (1)
   runLen[i-2] > runLen[i-1]                 (2)
   

   違反時觸發合併：優先合併較小的相鄰分區，避免大分區重複參與合併（類似 Huffman 編碼思想）。
4. 膽怯歸併： 合併前用二分查找確定複製範圍，跳過已有序的公共前綴/後綴。
5. 臨時數組複用： 全局分配一次 new Object[n/2]，歸併時交換角色，減少 GC 壓力。

Java 源碼關鍵邏輯

1. 入口 TimSort.sort()

// 計算 minRun
int minRun = minRunLength(nRemaining);
do {
    // 1. 獲取下一個 run（含反轉遞減 run）
    int runLen = countRunAndMakeAscending(a, lo, hi);
    // 2. 過短 run 用二分插入排序擴充
    if (runLen < minRun) {
        int force = Math.min(minRun, nRemaining);
        binarySort(a, lo, lo + force, lo + runLen);
        runLen = force;
    }
    // 3. 壓入棧
    ts.pushRun(lo, runLen);
    // 4. 檢查不變量，必要時合併
    ts.mergeCollapse();
    lo += runLen;
    nRemaining -= runLen;
} while (nRemaining != 0);
// 5. 強制合併剩餘所有 run
ts.mergeForceCollapse();

2. 合併決策 mergeCollapse()

private void mergeCollapse() {
    while (stackSize > 1) {
        int n = stackSize - 2;
        if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
            if (runLen[n-1] < runLen[n+1]) n--; // 合併較小的那對
            mergeAt(n);
        } else if (runLen[n] <= runLen[n+1]) {
            mergeAt(n);
        } else {
            break; // 滿足不變量
        }
    }
}

3. 膽怯歸併 mergeLo/mergeHi

• 複製較短的 run 到臨時數組。
• 二分查找目標元素在另一 run 中的插入位置，跳過無需比較的元素（gallop 模式）。
• 連續 MIN_GALLOP = 7 次命中切換到膽怯模式，否則回退普通逐個比較。

性能對比

應用場景與避坑

• 適用： 通用對象排序、數據含有序片段、要求穩定性。
• 不適用： 基本類型數組（Java 用雙軸快排）、極小數組（<47 用插入排序）、內存極受限環境。
• 避坑： 比較器必須滿足**傳遞性**與**一致性**，違反會導致 IllegalArgumentException: Comparison method violates its general contract。