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<String> list = Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "x", "j");虽然中间插入了一个较大的 "x"，Timsort 会快速识别前 9 个为升序 run，把 "x" 和 "j" 单独成 run 或组合后归并，远快于从头比较的快排。这种适应性正是它被选为默认算法的核心原因。
