 用的是 Timsort——一种"先找有序段、再把有序段归并起来"的混合排序算法。它在最好情况下只要 O(n)（数据本来就接近有序），最坏情况也是稳定的 O(n log n)，而且是稳定排序。三个特性叠在一起，让它成了现实数据（大量部分有序）上的最优解之一。下面用四个实验，把它的运作方式拆开看。

1. 先看一个反常现象：接近有序的数据，排序快得离谱

import random, time

# 数据 A：完全随机
a = [random.random() for _ in range(100000)]

# 数据 B：基本有序，只打乱 1% 的元素
b = list(range(100000))
for _ in range(1000):
    i, j = random.randrange(100000), random.randrange(100000)
    b[i], b[j] = b[j], b[i]

t0 = time.perf_counter(); a.sort(); t1 = time.perf_counter()
t2 = time.perf_counter(); b.sort(); t3 = time.perf_counter()
print(f'随机数据：{(t1-t0)*1000:.1f} ms')
print(f'接近有序：{(t3-t2)*1000:.1f} ms')

随机数据：48.2 ms
接近有序：6.9 ms

同样的十万个元素，只把"有序程度"改了改，速度差了 7 倍。

 普通快排在这里帮不上忙——它的分区操作可不关心你数据有序无序，永远老老实实 O(n log n)。Timsort 能吃到这个红利，靠的是它独特的两段式结构。

2. 第一步：run——先把数据切成"天然有序段"

Timsort 开工第一件事，不是比较，是

。它从左往右找"本来就递增（或严格递减）的连续段"，每个段叫一个 

data = [1, 3, 5, 7, 2, 4, 6, 9, 8]
# 扫描结果：
# run1 = [1, 3, 5, 7]   天然递增，白捡
# run2 = [2, 4, 6, 9]   天然递增，白捡
# run3 = [8]            长度不够，后面讲

数据里的"有序片段"是被直接认领的，

。现实数据为什么快？因为现实数据到处是有序片段：时间序列、日志、按某字段排过的表、甚至只是"大部分人对的"——run 越长，归并的趟数越少。

成递增段收编——反正反转是 O(n) 且不破坏稳定性，白捡一个 run 干嘛不要。

：扫描出的 run 如果太短（不足最小长度，通常 32~64），Timsort 会用

把它强行续长到最小长度。为什么是插入排序？因为短段上插入排序常数极小，而且稳定——这两点正是下一步归并最需要的。

3. 第二步：merge——把有序段两两归并

有了若干个有序段，剩下就是经典的

：两个有序序列合成一个有序序列，每个元素只看一次，O(n) 搞定。

[1, 3, 5, 7]  +  [2, 4, 6, 9]  →  [1, 2, 3, 4, 5, 6, 7, 9]

但 Timsort 的归并段位管理有个聪明设计——

。新产生的 run 压栈，每次压完检查栈顶几个 run 的长度是否满足约束，不满足就

为什么这么设计？如果无脑"等所有 run 找齐再一次性归并"，内存里要同时驻留全部 run；而用栈

，内存占用可控，合并次序也更有计划性。这是 Timsort 能在超大数组上稳定工作的关键。

4. 关键性质：稳定，而且知道" gallop 模式"

Timsort 有两个性质值得单独说。

 相等元素的相对顺序在排序后保持不变：

pairs = [(1, 'a'), (2, 'b'), (1, 'c'), (2, 'd')]
sorted(pairs, key=lambda p: p[0])
# [(1, 'a'), (1, 'c'), (2, 'b'), (2, 'd')]
# 两个 1、两个 2 的内部顺序都没变

段（相等元素不会被切开），归并时

。两个细节合力，才保住稳定性。Python 官方把"稳定"写进语言承诺，

 你敢拿去做多级排序，靠的就是它。

 归并过程中如果发现"某个 run 的元素连续大批量地小于另一个 run 的当前元素"，Timsort 不等一个一个比，直接

left  = [1, 2, 3, ..., 900]
right = [950, 951, ..., 999]

这种形态下，right 的前 50 个元素会被 gallop 一次抱走，而不是傻比 50 次。

这就是为什么"两段拼一块"的数据 Timsort 也吃得开

——真实数据里的有序块，经常是一出手就连续赢。

5. 和快排比：一张表看定位差异

快排不是输在平均性能，是输在

：最坏劣化、不稳定、不认有序数据。Timsort 用"多花一份归并内存"换来这三样——在现实世界，这笔交易几乎总是划算的。Java、Python、Android、V8 纷纷投奔 Timsort，就是这个道理。

6. 实战启示：怎么让 sorted 替你省时间

知道底层机制，用法上就能占便宜：

排序算法学了十几种，最后工业界选中的是这位"会认数据脸色"的。看懂 Timsort，你就看懂了算法工程化的核心思路：

不追求理论极限，追求现实数据上的最优期望

*上一篇：《用了三年 Python，我才知道 __slots__ 能让对象瘦身一半：一个内存实验讲透》。关注不迷路。*

结论先行：Python 的 sorted 和 list.sort 用的是 Timsort——一种"先找有序段、再把有序段归并起来"的混合排序算法。它在最好情况下只要 O(n)（数据本来就接近有序），最坏情况也是稳定的 O(n log n)，而且是稳定排序。三个特性叠在一起，让它成了现实数据（大量部分有序）上的最优解之一。下面用四个实验，把它的运作方式拆开看。

Python 的 sorted 为什么又快又稳？Timsort 的归并秘密一次讲透

Timsort 先扫有序段再归并，最好 O(n)、最坏 O(n log n) 且稳定，这就是 Python sorted 又快又稳的原因。

编程语言

Timsort作为Python官方排序算法，通过识别有序段（run）并智能归并，在部分有序数据上实现最高7倍提速。它兼具最好O(n)时间、稳定O(nlogn)最坏性能和稳定排序特性，成为处理现实数据的最优解。掌握其运作原理，能有效利用sorted的高效性，避免常见排序误区。

Android

Python

Java

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

Python 的 sorted 为什么又快又稳？Timsort 的归并秘密一次讲透

Python 的 sorted 为什么又快又稳？Timsort 的归并秘密一次讲透

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐