Java源码中的排序算法(五)-TimSort之扩展

上一篇整体了解了TimSort我们来彻底讲清楚：当 Timsort 遇到一个“太短”的天然 run 时，它是如何“扩展”它的？扩展的内容是什么？是否临时？会不会被删除？

一、为什么需要“扩展短 run”？

Timsort 设定一个阈值 MIN_MERGE（JDK 21 中为 32）。如果识别出的天然 run 长度 < 32，Timsort 不会直接使用它，而是会用插入排序将其“扩展”成一个长度 ≥32 的有序段。

为什么要这么做？

• 小数组上，插入排序比归并更高效（常数因子小，缓存友好）；
• 避免产生大量极短 run，导致后续归并栈过深、合并次数爆炸；
• 保证每个 run 足够“饱满”，使 galloping 模式等优化能有效工作。

简单说：“与其合并 10 个长度为 3 的 run，不如先花一点代价把它们变成 1 个长度为 30 的 run。”

二、扩展操作的本质：就地排序（In-place Sorting）

核心结论（先说答案）：

扩展操作是“就地”的——它直接在原数组上对 [runStart,runEnd+extra] 这一段进行排序，生成一个新的、更长的有序 run。这个新 run 是最终结果的一部分，不是临时数据，也不会被删除。

具体过程（以 JDK 21 源码为例）

假设：

• 当前天然 run 是 [a[5],a[6],a[7]]（长度 = 3）
• MIN_MERGE=32
• 所以需要再取 32-3=29 个元素，即处理区间 [5,5+32)=[5,37)

Timsort 会调用：

binarySort(a, lo, lo + minRun, runHi, c);

其中：

• lo=5（run 起始）
• lo+minRun=37（目标结束位置）
• runHi=8（天然 run 结束位置，即 5+3=8）

binarySort 做了什么？

// binarySort(a, 5, 37, 8, c)// 含义：对 a[5..37) 排序，且已知 a[5..8) 已经有序private static <T> void binarySort(T[] a, int lo, int hi, int start, Comparator<? super T> c) {    if (start == lo) start++; // 如果整个区间都无序，从第二个元素开始    // 从 start 开始，逐个将元素插入到前面的有序部分    for (; start < hi; start++) {        T pivot = a[start]; // 取当前元素        // 在 a[lo..start) 中二分查找 pivot 的插入位置        int left = lo, right = start;        while (left < right) {            int mid = (left + right) >>> 1;            if (c.compare(pivot, a[mid]) < 0)                right = mid;            else                left = mid + 1;        }        // 将 a[left..start) 整体右移一位        System.arraycopy(a, left, a, left + 1, start - left);        // 插入 pivot        a[left] = pivot;    }}

举个例子

原始数组片段（索引 5~36）：

天然有序部分（run）:[10,20,30]← a[5..8)
后续无序部分:[5,25,15,40,...]← a[8..37)

binarySort 执行后：

整个 a[5..37)变成一个**完全有序**的序列：
[5,10,15,20,25,30,40,...]

关键点：

• 输入：前 3 个有序 + 后 29 个无序
• 输出：32 个完全有序
• 位置：仍在原数组的 [5,37) 位置
• 性质：这是一个新的、合法的、最终的有序 run

三、“扩展”可能存在的歧义

Q1: “扩展产生的内容是什么？”

A: 是对原数组中 [runStart,runStart+minRunLen) 这一段重新排序后的结果。它融合了原有的天然有序部分和后续的无序部分，形成一个更长的有序段。

Q2: “是临时的吗？”

A: 不是临时的！ 它直接写回原数组，是最终排序结果的一部分。Timsort 是 in-place 算法（除归并时的临时 buffer 外），所有 run 都在原数组上构建。

Q3: “会在最后删除吗？”

A: 完全不会删除！ 这个扩展后的 run 会被压入 run 栈，参与后续的归并过程，最终成为全局有序数组的一个组成部分。

四、为什么可以安全地“覆盖”后续元素？

你可能会担心：“后续元素还没处理，就被排序进来了，会不会丢数据？”

不会！原因如下：

1. Timsort 是顺序扫描的它从左到右处理数组， binarySort 扩展的范围 [lo,lo+minRun) 是尚未被识别为独立 run 的区域，属于“待处理区”。
2. 扩展长度是可控的minRun=min(MIN_MERGE,remainingLength)，确保不会越界。
3. 后续 run 从 lo+minRun 开始扩展完成后，下一个 run 的扫描起点就是 lo+minRun，不会重复处理。

类比：就像你整理书架，先把前 32 本书排好序放左边，再处理剩下的。你并没有丢书，只是提前整理了一部分。

五、图解整个流程

初始数组: [ ... | NATURAL_RUN (len=3) | UNPROCESSED (len=100) | ... ]                ↑ lo=5               ↑ start=8Step 1: 识别天然 run → len=3 < 32 → 需要扩展Step 2: 取 minRun = min(32, 103) = 32        → 目标区间: [5, 37)Step 3: binarySort(a, 5, 37, 8, c)        → 对 a[5..37) 排序，利用 a[5..8) 已有序的特性结果:    [ ... | NEW_SORTED_RUN (len=32) | UNPROCESSED (len=71) | ... ]                ↑                        ↑                下一个 run 从这里开始

六、总结：扩展操作的本质

一句话记住：“扩展”不是“复制一份临时数据”，而是“提前对下一段数据做局部排序”，让它变成一个合格的 run，参与后续归并。

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