Java Collections.sort()在JDK 7起改用TimSort：先识别自然有序段、动态计算minRun、小段用二分插入排序、栈式归并优化，兼顾性能与稳定性，对部分有序数据接近O(n)，但仅适用于对象数组。

Java 的 Collections.sort() 在 JDK 7 中完成了一次关键演进：从基于归并排序（MergeSort）切换为 TimSort。这不是简单替换，而是针对真实场景数据特征所做的深度优化。

为什么放弃传统 MergeSort？

MergeSort 虽稳定、时间复杂度可控（O(n log n)），但存在明显短板：

• 对已排序或近似有序的数据无加速能力，仍强制拆分-合并，浪费大量比较与拷贝
• 需要额外 O(n) 空间，在内存敏感场景下代价较高
• 无法利用现实数据中常见的“有序片段”（如升序子段、降序子段、小数组块）

TimSort 的核心设计思想

TimSort 是 Python 创始人 Tim Peters 为 CPython 设计的混合稳定排序算法，后被 Java 借鉴。它本质是“增强版归并排序”，关键创新在于：

• 识别自然有序段（run）：扫描输入，自动识别升序或严格降序的连续子序列（降序段会被原地反转成升序）
• 最小运行长度（minRun）动态计算：根据数组长度决定最小 run 长度（通常为 32–64），确保后续归并阶段的平衡性
• 插入排序预处理小段：对每个 run 内部若长度 ≤32，直接用二分插入排序（Binary Insertion Sort）整理，高效且低开销
• 归并栈与归并规则：用栈管理待归并的 run，归并时遵循 a ≥ b + c 等启发式规则，避免退化归并链，保持栈中 run 尺寸近似几何增长

Collections.sort() 在 JDK 中的实际表现

JDK 7+ 对 Collections.sort(List) 和 Arrays.sort(Object[]) 统一采用 TimSort。效果显著：

• 对完全有序、逆序、部分有序、含重复值等常见用例，性能提升 20%–50%，甚至接近 O(n)
• 最坏情况仍为 O(n log n)，但常数因子更优，实际耗时更低
• 仍保持稳定排序语义（相等元素相对位置不变），满足 Java 规范要求
• 无需用户干预——开发者调用方式完全不变，底层自动启用优化

你需要注意的细节

尽管 TimSort 更智能，但仍有几个实践要点：

• 自定义 Comparator 必须满足“传递性、自反性、对称性”，否则 TimSort 可能因错误的 run 判定或归并逻辑导致结果异常
• 对基本类型数组（如 int[]），Arrays.sort() 使用双轴快排（Dual-Pivot Quicksort），不走 TimSort；只有对象引用数组才触发 TimSort
• 小列表（如 size