TimSort通过单次线性扫描识别升序（a[i]≤a[i+1]）或严格降序（a[i]>a[i+1]）run，遇断点即切分；对短于minrun（32–64间动态计算）的run用插入排序扩展，确保归并高效。
因为 list.sort() 和 sorted() 底层用的是 TimSort，它不靠“猜”数据分布，而是直接扫描、识别并复用已有的有序片段（run），省掉大量冗余比较和移动。
TimSort 怎么识别局部有序的 run
它从左到右线性扫描一次数组，对每个位置判断是否延续当前 run：
- 升序 run 要求
a[i] （允许相等，保障稳定性） - 降序 run 要求
a[i] > a[i+1]（必须严格递减，否则反转会破坏相等元素顺序） - 遇到不满足条件的位置就切分，形成新 run —— 这一步是 O(n) 的，且只做一次
例如 [1,2,3,5,4,6,7,8] 会被识别为两个 run：[1,2,3,5] 和 [4,6,7,8]，中间那个 5 > 4 就是断点。后续归并只需合并这两个已排好序的块，跳过所有内部排序开销。
短 run 为什么不会拖慢性能
TimSort 不会放任太短的 run 进入归并阶段，它设了动态阈值 minrun（通常在 32–64 之间），并强制扩展短 run：
立即学习“Python免费学习笔记（深入）”；
macOS UI 自动化技能包 —— 用 Python 控制你的 Mac
下载
让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限
- 若检测到长度 minrun 长度
- 插入排序在局部有序段上极快（接近 O(k)，k 是扩展长度），远快于重新归并
-
minrun不是硬编码，而是根据总长计算得出，目的是让最终 run 数量接近 2 的幂，减少归并栈深度
这意味着：哪怕你传入一个「几乎有序但夹杂几个错位元素」的列表，TimSort 也只在错位点附近做少量插入操作，而不是像快排那样反复分治整个数组。
为什么手写快排在局部有序时容易崩
典型递归快排（尤其 pivot 固定选首/尾）在升序输入下会退化：
- 每次 partition 只把最小/最大元素拎出来，剩下 n−1 个仍保持升序
- 递归深度达到 O(n)，比较次数飙升至 O(n²)
- Python 默认递归限制约 1000 层，
list.sort()却完全不受影响
而 TimSort 对升序输入的处理就是「扫一遍确认有序 → 直接返回」，时间复杂度稳稳落在 O(n)。这不是优化技巧，是算法设计前提——它从不假设数据随机，而是默认数据有结构。
最容易被忽略的性能陷阱
降序数据里混入重复相邻元素（如 [5,5,4,4,3,3]）会让 TimSort 失去降序 run 识别能力，被迫切成大量单元素或双元素 run，归并开销暴增。这不是 bug，是稳定性的代价——你得自己决定：要绝对稳定性，还是为特定降序场景预处理（比如先去重再反转）。
