是的，python 的 sorted() 和 list.sort() 平均与最坏时间复杂度均为 o(n log n)，但基于 timsort 实现，在小数组、部分有序或含重复元素时可接近 o(n)；sorted() 返回新列表，list.sort() 原地排序。
Python 的 sorted() 和 list.sort() 确实是 O(n log n) 吗？
是的，但只在“平均情况”和“最坏情况”下成立；实际运行中，小数组、部分有序数据或重复元素多时，它会明显快于理论下界，甚至接近 O(n)。这不是 bug，而是 Timsort 的设计特性。
CPython 实现的排序算法是 Timsort —— 一种混合稳定排序，结合了归并排序和插入排序。它专为真实世界数据（常局部有序）优化。
-
sorted()返回新列表，list.sort()原地修改，时间复杂度一致 - 最坏情况仍是 O(n log n)，比如严格逆序；但比纯归并或堆排序常数更低
- 对已排序或近似排序的列表，Timsort 能检测“run”，直接跳过大量比较，实测可能只要 O(n)
- 注意：O(n log n) 是比较次数的渐进上界，不包括内存分配或对象比较开销（比如
str比较本身是 O(k)，k 是字符串长度）
什么时候会退化到真· O(n log n)，甚至更慢？
当输入刻意构造、破坏 run 检测机制时，Timsort 会退回到归并主干逻辑，此时比较次数逼近理论上限。但更常见的“变慢”其实来自你没意识到的隐式开销。
- 自定义
key函数：如果key=lambda x: heavy_computation(x)，那耗时主要在 key 计算，而非排序本身 - 不可哈希/不可比较对象：比如含 NaN 的 float 列表，或自定义类未实现
__lt__，会触发异常或回退到低效路径 - 极小列表（n
- 内存压力大时：Timsort 需要 O(n) 额外空间（归并阶段），在内存受限环境可能触发频繁 GC，拖慢整体
sorted() 的 key 和 reverse 怎么影响性能？
key 是最大变量源；reverse 几乎无代价 —— 它只是翻转比较逻辑，不改变数据移动次数。
立即学习“Python免费学习笔记（深入）”；
-
key被调用恰好 n 次（预计算），不是每次比较都调用；所以尽量让key是轻量函数（如attrgetter('id')优于lambda x: x.id） - 避免在
key中做 I/O、网络请求、正则匹配等 —— 这些会让 O(n log n) 失去意义 -
reverse=True不增加复杂度，但若你先sorted(..., reverse=False)再reversed()，就多一次遍历，纯属多余 - 多个排序条件？用元组：
key=lambda x: (x.status, -x.priority)，比两次sort()稳定且快
想验证某次排序是不是真 O(n log n)，该看什么？
别只看 wall-clock 时间 —— 它受缓存、GC、系统负载干扰太大。真正可比的是比较次数和移动次数，而 Python 不直接暴露这些。务实做法是：
- 用
timeit测不同规模 n 下的耗时，画 log-log 图；斜率接近 1 才说明是 O(n log n) - 对同一数据多次排序，确认是否稳定（Timsort 稳定，相同 key 的元素相对位置不变）
- 怀疑 key 开销大？单独测
[key(x) for x in data]耗时，再和总排序时间对比 - 极端 case 测试：用
list(range(10**6))[::-1]（逆序）和list(range(10**6))（正序）对比，差距可达 5–10 倍
真正容易被忽略的是：你写的“排序”逻辑里，90% 时间可能花在构造待排序列表、序列化、或 key 函数里，而不是 sorted() 本身。先 profile，再优化。
