Python内置sort快因调用C实现的Timsort；手写快排在升序/降序、大量重复元素、小数组等场景易退化，而Timsort通过识别run、三路归并、gallop模式高效应对；除非数据结构特殊、key无法表达且已确认sorted是瓶颈，否则不应手写。
Python内置list.sort()和sorted()为什么快
因为它们调用的是C语言实现的Timsort，不是Python写的循环或递归。哪怕你把快排写得再“正确”，只要在Python层做比较、交换、切片，就天然比C层慢一个数量级——这不是算法问题，是解释器开销问题。
自己写quicksort在哪些场景会明显变慢
常见错误现象：RecursionError、排序耗时暴涨10–100倍、内存占用突增。这些往往不是代码逻辑错，而是没应对现实数据特征：
- 输入已是升序/降序：手写递归快排退化为O(n²)，
list.sort()直接识别run，接近O(n) - 含大量重复元素：手写快排partition易失衡，Timsort用三路归并+gallop模式跳过重复段
- 小数组（
- 混合类型或自定义对象：手写快排要反复调用
__lt__，而Timsort在C层批量比较，避免Python对象调用栈膨胀
Timsort如何决定用哪种子策略
它不靠配置，而是在扫描输入时动态决策：
- 先扫描找“自然run”：连续升序或严格降序片段（降序会被反转），长度不足
minrun（通常32）的，用插入排序补足 - 维护一个run栈，合并时检查x > y + z等条件，避免不平衡归并；满足则触发gallop模式（指数跳跃比较）
- 整个流程无Python层循环——所有扫描、插入、归并都在C代码里完成，连临时数组分配都复用内存池
什么时候真该自己写排序
极少。除非你明确知道以下全部成立：
立即学习“Python免费学习笔记（深入）”；
- 数据结构特殊（比如链表、磁盘文件流），无法用
list承载 - 排序逻辑不能表达为
key函数（例如依赖外部状态或副作用） - 你已用
cProfile确认sorted()是瓶颈，且能用Cython或C扩展重写
否则，写sorted(data, key=...)永远比手写快——不是因为它“更聪明”，而是它根本不在Python解释器里跑。
