现代语言里的排序：Python 用 Timsort，Java 用双轴快排，凭什么不一样

当你写 sorted([3,1,2]) 或 Arrays.sort(arr) 时，可能不会想：这两行代码背后是两套完全不同的算法。它们的选择，体现了排序工程的两种哲学。

Python：Timsort（稳定、自适应）。Python 的 list.sort() 与内置 sorted() 使用 Timsort（Tim Peters, 2002）。它的核心洞察是：真实世界的数据往往包含大量已有序的片段（run）。Timsort 先识别这些 run，再用经过调优的归并策略合并，并对短 run 用二分插入排序补齐。结果是：最好 O(n)（已排序）、最坏 O(n log n)、且稳定。由于 Python 重视"对象排序的稳定性"，Timsort 是首选。

Java：因类型而异。Java 对基本类型（int、double 等）数组用 双轴快速排序（Vladimir Yaroslavskiy, 2009）——它一次选两个基准把数组分成三段，比经典单轴快排减少比较次数，且基本类型不需要稳定性，可以放手优化速度；而对对象数组，Java 同样用 Timsort，因为对象排序通常需要保持稳定性。

为什么不一样？本质权衡是：要不要稳定 + 数据是否可能部分有序。需要稳定或常有有序片段 → Timsort；只追求裸速度且无需稳定 → 双轴快排。两者都把"小数组回退插入排序""避免最坏情况"等经验写进了实现。

有趣的是，这些现代算法并没有抛弃今天学的插入排序——恰恰相反，它们把插入排序当作最底层的"收尾工具"。学懂 B1，你才算真正看懂了每天都在用的 sort()。

图：Python 与 Java 排序实现的核心取舍

参考代码（Python）

Python 的 sorted 是稳定排序（Timsort），下面验证稳定性。

items=[('A',90),('B',70),('A',70),('B',90),('A',70),('B',70)]
by_salary=sorted(items, key=lambda x: x[1])     # 先按工资升序
by_dept=sorted(by_salary, key=lambda x: x[0])   # 再稳定地按部门排
# 同部门内仍保持刚才的工资升序 —— 不稳定排序会打乱它
print(by_dept)

关联推荐

• 从冒泡到快排 — 快排思想如何演进到双轴快排
• 哈希表：为什么 Redis、Python 字典都靠它"秒查" — Python 内部的另一处工程智慧
• 算法通关训练营·入门篇 — 从基础排序进阶到工程实现