Python 的 sorted() 和 list.sort() 使用 Timsort 算法，一种结合插入排序与归并排序的稳定混合算法，专为部分有序数据优化，两者底层实现相同，仅在是否原地排序上不同。
Python 的 sorted() 和 list.sort() 用的是什么算法
Python 标准库的排序不是手写的快排或归并，而是 Timsort —— 一种为真实数据（尤其部分有序）优化的混合稳定排序算法，由 Tim Peters 为 Python 设计。它结合了归并排序和插入排序，在小数组或局部有序段上切片使用插入排序，再用归并合并。这意味着：
-
sorted()返回新列表，list.sort()原地修改，两者底层都调用同一套 Timsort 实现 - 最坏时间复杂度仍是
O(n log n)，但现实中多数场景（如已排序、逆序、含重复块）性能远优于纯快排 - 稳定：相等元素的相对位置不会改变，这对多级排序（比如先按年龄、再按姓名）很关键
什么时候该用 key 参数而不是自己写比较逻辑
直接传 key 函数比写 cmp_to_key 或自定义 __lt__ 更安全、更高效。Timsort 内部只调用 key 一次/元素，而旧式 cmp 方式（Python 2 风格）在每次比较时都执行函数，开销大且易出错。
- 升序按字符串长度：
sorted(words, key=len) - 降序按绝对值：
sorted(nums, key=abs, reverse=True) - 多字段：先按姓氏再按名字，
key=lambda x: (x.last, x.first) - 避免踩坑：不要在
key中做副作用操作（如修改全局状态），它可能被多次调用（尽管 Timsort 会缓存结果，但行为不保证）
sorted() 在字典和生成器上的行为差异
字典本身不可排序，但 sorted() 可对它的键、值或项视图排序；生成器则必须转成序列才能排序，否则会报 TypeError: 'generator' object is not subscriptable。
- 按字典键排序：
sorted(d.keys())或直接sorted(d) - 按键排序并保留键值对：
sorted(d.items(), key=lambda kv: kv[0]) - 生成器必须先收集：
sorted((x*2 for x in range(10)))是合法的，因为sorted()内部会先转成列表；但sorted(range(10**7))会吃掉大量内存，此时应考虑是否真需要全量排序 - 注意：空生成器没问题，
sorted(())或sorted([])都返回空列表，类型一致
自定义对象排序时 __lt__ 和 key 的取舍
如果类设计之初就明确“天然有序”（比如 Point 按欧氏距离、Date 按时间先后），实现 __lt__ 更自然；如果只是临时按某字段排序（比如调试时按 obj.debug_id 查看），用 key 更轻量、不侵入类定义。
- 只实现
__lt__就够了：sorted()能自动推导其他比较关系（通过@total_ordering装饰器可补全） - 若同时支持多种排序逻辑，硬编码
__lt__反而僵化；这时key是唯一合理选择 - 性能上无实质差别，但
key更易测试、更易组合（比如key=lambda x: (x.status, -x.priority)） - 容易忽略的一点：如果对象有
__lt__但逻辑有 bug（比如未处理None），排序过程可能抛TypeError且堆栈不直观；key的错误更容易定位
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
