Java源码中的排序算法(六)-TimSort之天然存在的run

在之前的 Java源码中的排序算法（四）-TimSort 讲解中，“如何识别天然存在的升序或降序 run” 这一关键步骤确实讲得不够透彻。下面我将进一步学习 Timsort 是如何扫描并找出这些天然有序片段（run）的，并结合 JDK 21 源码说明其精妙设计。

Timsort的核心步骤

1. 扫描并识别自然run
2. 扩展短run至最小长度
3. 用栈管理run并智能合并
4. 归并时启用galloping模式

根据Timsort的核心步骤 的第一步不是“分割数组”，而是向右扫描，尽可能延长当前已有的有序序列。这个过程由 countRunAndMakeAscending 方法完成（位于 java.util.TimSort 类中）。

JDK 21 源码详解

privatestatic <T> intcountRunAndMakeAscending(    T[] a, int lo,        // 当前 run 起始位置int hi,        // 数组上界（不包含）    Comparator<? super T> c){assert lo < hi;int runHi = lo + 1; // 至少有一个元素（a[lo]）// 如果数组只有一个元素，直接返回长度 1if (runHi == hi)return1;// 【关键判断】：看前两个元素是升序还是降序？if (c.compare(a[runHi], a[lo]) < 0) { // 情况1️⃣：a[lo+1] < a[lo] → 发现【降序】趋势！        runHi++; // 继续向右扩展// 向右扫描，只要还在严格降序，就继续while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)            runHi++;// 【重要操作】：将整个降序段反转为升序！        reverseRange(a, lo, runHi);    } else { // 情况2️⃣：a[lo+1] >= a[lo] → 发现【非严格升序】趋势        runHi++;// 向右扫描，只要是非严格升序（允许相等），就继续while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)            runHi++;    }// 返回这个 run 的长度return runHi - lo;}

关键逻辑拆解

1. 只看前两个元素，决定方向

• Timsort 不会预先假设数据是升序还是降序。
• 它只比较 a[lo] 和 a[lo+1]：
• 如果 a[lo+1] < a[lo] → 判定为“降序段”
• 否则（>=）→ 判定为“升序段”

💡 为什么允许相等？因为 Timsort 是稳定排序，相等元素必须保持原顺序。所以升序段定义为 a[i] <= a[i+1]（非严格升序）。

2. 向右贪婪扩展

• 一旦确定方向，就尽可能向右延伸，直到有序性被打破。
• 例如：

  [10, 8, 6, 4, 5, 3, ...]       ↑ 在这里停止（4 < 5 打破降序）

  找到的 run 是 [10, 8, 6, 4]，然后立即反转为 [4, 6, 8, 10]。

3. 降序段立即反转

• Timsort 内部只处理升序 run。
• 所有降序段在识别后立刻原地反转，变成升序。
• 这样后续的归并逻辑可以统一处理，无需区分方向。

✅ 优势：反转操作是 O(k)（k 为 run 长度），但避免了在归并时处理两种方向的复杂逻辑，简化了核心算法。

举个完整例子

原始数组（从索引 0 开始）：

[5, 3, 1, 2, 4, 9, 8, 7]

Step 1: 扫描第一个 run（从 index=0）

• 比较 a[1]=3 vs a[0]=5 → 3 < 5 → 降序
• 向右扩展：3 > 1 → 继续；1 < 2 → 停止
• 找到降序段：[5, 3, 1]
• 立即反转 → [1, 3, 5]
• 返回 run 长度 = 3

Step 2: 下一个 run 从 index=3 开始

• 比较 a[4]=4 vs a[3]=2 → 4 >= 2 → 升序
• 向右扩展：4 < 9 → 继续；9 > 8 → 停止
• 找到升序段：[2, 4, 9]
• 无需反转
• 返回 run 长度 = 3

Step 3: 下一个 run 从 index=6 开始

• 比较 a[7]=7 vs a[6]=8 → 7 < 8 → 降序
• 到达数组末尾，停止
• 找到降序段：[8, 7]
• 反转 → [7, 8]
• 返回 run 长度 = 2

最终得到三个升序 run：

[1, 3, 5] | [2, 4, 9] | [7, 8]

接下来，Timsort 会用栈管理这些 run，并按策略合并。

特殊情况处理

• 完全无序的小数组：如果 run 长度 < MIN_MERGE（32），Timsort 会用 binarySort 将其扩展为有序段。这相当于“人工制造一个长 run”。

• 全相等数组：整个数组会被识别为一个超长 run（因为 a[i] >= a[i-1] 恒成立），排序直接结束 —— O(n) 时间！

• 交替升降序列：如 [1,3,2,4,3,5,...]，每个 run 长度仅为 2 或 3，此时 Timsort 退化为普通归并排序，但仍保证 O(n log n)。

总结：Timsort 识别 run 的精髓

1. 起点试探：用前两个元素判断升/降序趋势；
2. 贪婪延伸：沿该趋势尽可能向右扩展；
3. 降序反转：立即将降序段转为升序，统一内部表示；
4. 返回长度：供后续决定是否需要扩展或合并。

这一过程完全自适应，无需任何参数调整，就能在 O(n) 时间内将任意数组分解为若干升序 run。正是这种对“真实数据特性”的尊重和利用，让 Timsort 成为了工程界的排序标杆。

💡 感谢你看完这篇内容，这是我自己在工作学习中遇到的case，做一些简单的 研究，并总结经验，如有遗漏或不合理的地方，欢迎你提出问题，让我们一起探索