Java源码中的排序算法(三)-TimSort

在文章 Arrays.sort() 中提到引用类型使用了TimSort，现在就来揭开 Timsort 的神秘面纱。

“

“I believe that lists very often do have exploitable partial order in real life, and this is the strongest argument in favor of timsort”—— Tim Peters（Timsort 作者）

通过阅读做作者原始的设计文档，文中也一语道破TimSort的核心设计理念（公众号发送TimSort 获取原始设计文档）

”

https://svn.python.org/projects/python/trunk/Objects/listsort.txt?spm=5176.28103460.0.0.38f97d83P1I65F&file=listsort.txt

一、Timsort 是什么？

Timsort 是一种自适应的、稳定的归并排序变体，由 Python 社区的 Tim Peters 于 2002 年设计。如今，它已成为多个主流语言的标准排序算法：

在 JDK 中，当你对对象数组（如 String[]、List<Employee>）排序时，底层调用的就是 java.util.TimSort。而基本类型数组（如 int[]）则使用 DualPivotQuicksort——因为对象排序必须稳定，而基本类型不需要。

二、核心逻辑：四步走策略

Timsort 的核心思想是：识别并合并数据中已有的有序片段（run），而非盲目分割。整个过程分为四个阶段：

1️⃣ 扫描并识别自然 run

从左到右扫描数组，找出天然存在的升序或降序子序列（称为 run）。如果是降序，立即反转为升序。

2️⃣ 扩展短 run 至最小长度

如果 run 长度小于 MIN_MERGE（JDK 21 中为 32），则用二分插入排序将其扩展到至少该长度。

3️⃣ 用栈管理 run 并智能合并

将 run 压入栈，维护两个不变式确保合并操作平衡：

• runLen[i-3] > runLen[i-2] + runLen[i-1]
• runLen[i-2] > runLen[i-1]

4️⃣ 归并时启用 galloping 模式

当一个 run 的多个连续元素整体小于另一个 run 时，切换到指数搜索 + 二分查找的 galloping 模式，大幅减少比较次数。

三、核心逻辑的核心代码（JDK 21）

1. 识别并规范化 run

// TimSort.javaprivatestatic <T> intcountRunAndMakeAscending(T[] a, int lo, int hi, Comparator<? super T> c){assert lo < hi;int runHi = lo + 1;if (runHi == hi) return1;// 判断是升序还是降序if (c.compare(a[runHi++], a[lo]) < 0) { // 降序while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)            runHi++;        reverseRange(a, lo, runHi); // 反转为升序    } else { // 升序while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)            runHi++;    }return runHi - lo;}

“

💡 关键点：直接利用数据中的有序性，避免无谓分割。

”

2. 二分插入排序（扩展短 run）

privatestatic <T> voidbinarySort(T[] a, int lo, int hi, int start, Comparator<? super T> c){assert lo <= start && start <= hi;if (start == lo) start++;for (; start < hi; start++) {        T pivot = a[start];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;        }// 移动元素并插入        System.arraycopy(a, left, a, left + 1, start - left);        a[left] = pivot;    }}

“

为什么用二分插入？对小数组（<32 元素），它比归并更高效，且缓存友好。

”

作者 Tim Peters 的原始设计文档

3. 智能合并策略（维护栈不变式）

privatevoidmergeCollapse(){while (stackSize > 1) {int n = stackSize - 2;// 检查是否违反不变式if ((n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1]) ||            (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) {if (runLen[n - 1] < runLen[n + 1]) n--;        } elseif (runLen[n] > runLen[n + 1]) {break; // 不变式满足，退出        }        mergeAt(n); // 合并 run[n] 和 run[n+1]    }}

“

🛡️ 不变式的意义：防止大 run 合并小 run 导致性能退化，保证 O(n log n) 最坏情况。

”

4. Galloping 模式（加速归并）

privatevoidmergeLo(int base1, int len1, int base2, int len2){// ...int minGallop = this.minGallop;    outer:while (true) {// 正常模式：逐个比较// ...// 进入 galloping 模式do {assert len1 > 0 && len2 > 0;            count1 = gallopRight(a[base2], tmp, cursor1, len1, 0, c);// ... 处理 count1            count2 = gallopLeft(tmp[cursor1], a, base2, len2, 0, c);// ... 处理 count2if (count1 < MIN_GALLOP && count2 < MIN_GALLOP) {break outer; // 退出 galloping            }        } while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);    }}

四、为什么这么做？—— 设计哲学

1. 真实数据不是随机的

现实世界的数组往往包含：

• 已排序的子序列（如数据库按 ID 插入的记录）
• 重复元素（如状态字段）
• 局部有序（如按天分组的日志）

2. 稳定性是对象排序的生命线

想象一个场景：

// 先按部门排序employees.sort(Comparator.comparing(Employee::getDept));// 再按姓名排序employees.sort(Comparator.comparing(Employee::getName));

如果排序不稳定，第一次排序的结果会被第二次完全打乱。Timsort 保证稳定性，使多级排序成为可能。

3. 最坏情况不能妥协

快速排序在最坏情况下退化为 O(n²)，而 Timsort 通过智能合并策略，严格保证 O(n log n)，避免生产环境雪崩。

以上就是对TimSort的整体了解，后续我还将画一些时间深入学习它是怎么识别有序、扩展短run等核心步骤的，尽情关注

“

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

”