collections.sort() 对对象列表使用 timsort 算法，通过转为数组后调用 arrays.sort(object[]) 实现；它稳定、适应部分有序数据、最坏 o(n log n)，融合插入与归并排序并识别自然有序段。

Collections.sort() 对对象数组使用的确实是 Timsort 算法，但它不是“直接调用 Timsort”，而是通过 Arrays.sort(Object[]) 间接实现的——而该方法在 Java 7 及以后版本中，对非基本类型数组默认采用的就是 Timsort。

为什么是 Timsort 而不是其他排序？

Java 在 2011 年（JDK 7）将 Arrays.sort(Object[]) 的底层实现从传统的归并排序（MergeSort）切换为 Timsort，主要原因包括：

• Timsort 是稳定排序（相同元素的相对位置不变），这对对象排序很重要，尤其涉及业务逻辑依赖顺序时；
• 它在现实数据中表现极佳：对部分有序、小规模或已排序数组接近 O(n) 时间复杂度；
• 最坏情况仍是 O(n log n)，空间复杂度为 O(n)，与归并排序相当，但常数因子更优；
• 它融合了插入排序（处理小块）和归并排序（合并有序段），还引入了“run”识别机制，能自动发现升序/降序片段并翻转逆序段。

Timsort 在 Collections.sort() 中的实际运作流程

当你调用 Collections.sort(list)，且传入的是 ArrayList 或其他支持随机访问的 List 时，JVM 会：

• 先将 List 转为 Object[] 数组（通过 list.toArray()）；
• 调用 Arrays.sort(Object[], Comparator)（若提供比较器）或 Arrays.sort(Object[])（要求元素实现 Comparable）；
• 进入 Timsort 主循环：识别自然有序段（run），对短 run 插入排序补长至最小长度（minRun），再两两归并，使用栈管理合并顺序以保证稳定性与效率。

注意：对于 LinkedList 这类不支持高效随机访问的 List，Collections.sort() 会先复制到数组排序，再写回链表——所以时间上仍是 O(n log n)，但额外有 O(n) 空间开销。

你不需要手动干预，但需注意几个关键点

Timsort 很强大，但它的正确性高度依赖你的比较逻辑：

• Comparator 必须满足自反性、传递性、对称性（即严格遵守 Comparator 合约），否则可能抛 IllegalArgumentException 或产生未定义行为；
• 如果元素没有实现 Comparable，又没传 Comparator，运行时会抛 ClassCastException；
• Timsort 不改变原 List 的结构（比如 ArrayList 的底层数组引用），但会重排其内容；
• 它不是并行算法，Collections.sort() 始终是单线程执行（如需并行，请改用 list.parallelStream().sorted(...).collect(...)，底层用的是不同的并行归并策略）。

简单验证：你可以观察到 Timsort 的“痕迹”

例如对一个几乎有序的列表排序：

List list = Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "x", "j");

虽然中间插入了一个较大的 "x"，Timsort 会快速识别前 9 个为升序 run，把 "x" 和 "j" 单独成 run 或组合后归并，远快于从头比较的快排。这种适应性正是它被选为默认算法的核心原因。