Collections.sort()对对象列表排序底层使用TimSort算法，即先转为Object[]数组，再调用Arrays.sort(Object[])执行：识别自然有序段（run）、补长至minRun后插入排序、栈式归并，全程依赖Comparator且保持稳定性。
Collections.sort() 对对象列表排序时，底层实际执行的是 TimSort 算法——它不是独立实现，而是通过 list.toArray() 转为数组后，调用 Arrays.sort(Object[]) 完成的。这个过程稳定、自适应，且行为高度依赖你提供的比较逻辑。
TimSort 的三阶段执行流程
当你调用 Collections.sort(list, comparator)，JVM 内部会按以下步骤推进：
-
转数组与预扫描：先将 List（无论 ArrayList 还是 LinkedList）转为
Object[]；然后线性扫描，识别自然升序段（ascending run）或严格降序段（descending run），后者会被就地翻转并标记为升序段； -
补长与局部排序：对每个 run，若长度小于动态计算出的
minRun（通常 32–64），则用二分插入排序将其扩展至至少minRun长度，确保后续归并效率； -
栈式归并：维护一个栈记录已识别的 run，按特定规则（如
len[A] ≥ len[B] + len[C]）触发两两归并；归并过程中反复调用你的Comparator.compare()判断跨 run 边界的大小关系，最终完成整体有序。
稳定性不是“默认保留”，而是由 compare 返回 0 定义的
TimSort 是稳定算法，但它的“稳定”效果完全取决于你如何定义“相等”：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
- 只有当
compare(a, b) == 0时，a 和 b 才被视作“相等元素”，它们在原列表中的相对顺序才会被保留； - 若你写的是
(a, b) -> a.name.compareTo(b.name)，那么所有同名对象构成一组“相等元素”，排序后原始插入顺序不变； - 若你改成
(a, b) -> Integer.compare(a.age, b.age) * 10 + a.id - b.id，哪怕 age 相同，id 不同也会导致返回非零值——此时 TimSort 不认为它们相等，稳定性不生效。
影响执行正确性与性能的关键细节
TimSort 表现强大，但极易因 Comparator 编写不当而失效或变慢：
立即学习“Java免费学习笔记（深入）”；
- 避免整数溢出：
a.age - b.age在极端值下可能符号反转，误判大小；应统一用Integer.compare(a.age, b.age)； - 显式处理 null：
Objects.compare(a.field, b.field, Comparator.nullsLast(String::compareTo))比直接调用a.field.compareTo()更安全； - 禁止副作用：Comparator 必须是纯函数——不能修改对象字段、不能读取 volatile 变量、不能依赖系统时间或随机数；
- 预计算高开销字段：如果比较涉及字符串正则匹配或深层属性访问，提前缓存结果（如
normalizedKey），再用Comparator.comparing(Obj::getNormalizedKey)。
为什么 LinkedList 也能稳定排序？
即使传入的是 LinkedList，Collections.sort() 仍能保证稳定性：
- 内部会先复制全部节点到临时
Object[]数组； - 在数组上运行完整 TimSort 流程；
- 再按排好序的引用顺序，逐个写回链表节点；
- 整个过程不改变原始节点结构，仅重排链接顺序，因此原始相对位置关系依然可追溯并保留。
