Python sort()与sorted()性能对比：大数据量下谁更快

在大数据量下，list.sort() 的执行速度明显快于 sorted()，通常有 15% 至 30% 左右的时间优势，同时其额外内存开销恒定为近乎零（O(1) 辅助空间），而 sorted() 则必须额外开辟 O(N) 的内存空间来创建新列表。两者底层均运行高度优化的 Timsort（或 Python 3.11+ 结合的 Powersort）算法，核心比较与指针交换逻辑一致，速度差异的核心在于 sorted() 存在对象实例化、内存申请以及指针浅拷贝的额外固定成本。

核心机制差异：原地修改与新对象开辟

要理解大数据量下的速度差距，首先需要看清两者在内存层面的运作方式：

• list.sort() 是列表独有的就地方法（in-place method）：它直接操作原列表底层的 PyListObject 指针数组，在原数组上直接进行元素的指针重新排列。排序完成后方法返回 None，不需要申请新的列表头部，也不需要重新分配指针缓冲区。
• sorted() 是通用内置函数（built-in function）：它可以接受任何可迭代对象（如列表、元组、生成器、字典等）。为了保证输入不被修改，sorted() 在排序前必须首先在堆内存中新建一个 PyListObject，按照输入大小分配一块连续的指针数组，把所有元素的引用拷贝进去，再在新的缓冲区上执行排序，最后返回这个新列表。

严谨的基准测试方法与步骤

评估百万乃至千万级数据下的排序性能时，测试方式必须排除干扰项。常见错误是把“生成测试数据”或“为了让 sort() 多次运行而做的列表拷贝”耗时算进了排序本身。为了客观度量，应遵循以下五个标准步骤：

1. 数据离线预生成：提前生成测试所需的随机整数或浮点数列表，保存在内存中，避免将伪随机数生成器（如 random.randint）的计算开销计入测试。
2. 基线清理与 GC 控制：在每次测量前执行 gc.collect() 回收碎片，并在测量段开启 tracemalloc 记录内存峰值。
3. 数据副本隔离：因为 sort() 会破坏原列表的无序性（Timsort 对已排序列表耗时仅为 O(N)），所以在测试 sort() 时，必须用切片 data[:] 复制一份独立待测数据，但计时器仅包裹排序调用本身。
4. 多轮次稳定取样：使用 timeit 或单调纳秒时钟 time.perf_counter_ns() 进行多次重复执行，取多次测量的最小耗时或中位数，规避系统上下文切换的毛刺。
5. 双重指标对齐：同时输出耗时（ms）与增量峰值内存（MB），形成完整的性能剖面。

可复现的基准测试代码示例

下面的脚本可以在本地直接运行，用以检验不同数据规模下的时间与内存表现：

import random
import time
import tracemalloc
import gc

def benchmark_sort(size):
    print(f"--- 正在准备数据规模: {size:,} ---")
    raw_data = [random.randint(0, 10_000_000) for _ in range(size)]
    
    # 1. 测试 sorted()
    gc.collect()
    tracemalloc.start()
    t0 = time.perf_counter()
    res_sorted = sorted(raw_data)
    t_sorted = (time.perf_counter() - t0) * 1000
    _, peak_sorted = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    del res_sorted
    gc.collect()

    # 2. 测试 list.sort() (使用切片预先准备独立副本)
    target_list = raw_data[:]
    tracemalloc.start()
    t0 = time.perf_counter()
    target_list.sort()
    t_sort = (time.perf_counter() - t0) * 1000
    _, peak_sort = tracemalloc.get_traced_memory()
    tracemalloc.stop()

    print(f"sorted()    耗时: {t_sorted:7.2f} ms | 增量内存峰值: {peak_sorted / (1024*1024):6.2f} MB")
    print(f"list.sort() 耗时: {t_sort:7.2f} ms | 增量内存峰值: {peak_sort / (1024*1024):6.2f} MB")
    diff_pct = ((t_sorted - t_sort) / t_sort) * 100
    print(f"结论: list.sort() 比 sorted() 快 {diff_pct:.1f}%\n")

if __name__ == "__main__":
    for s in [100_000, 1_000_000, 5_000_000]:
        benchmark_sort(s)

实测数据呈现与深度分析

在 Python 3.11（64位 Linux / macOS，x86_64 / ARM64）标准运行环境下，采用上述方法对随机离散整数进行测试，不同规模下的典型测量数值如下表所示（实际数值依 CPU 频率与缓存大小略有浮动，但相对比例保持高度一致）：

为什么两者的渐进复杂度相同，耗时却有稳定差异？

在算法理论中，Timsort 的最坏与平均时间复杂度都是 O(N log N)。但“大 O 记法”忽略了隐藏在常数因子里的硬件与系统交互开销：

• 内存申请开销（Memory Allocation）：在 64 位系统下，一个拥有 1000 万元素的列表仅存储指针就需要 10,000,000 * 8 字节 ≈ 76.3 MB 的连续堆内存。操作系统和 Python 底层 pymalloc 在分配这种大块内存时，涉及查找合适页表、虚拟内存映射甚至触发缺页中断，这需要耗费数十毫秒。
• 浅拷贝与 CPU 缓存局部性：sorted() 必须先通过 C 语言级别的 memcpy 把千万个指针逐一复制到新地址空间。在数据量远超 CPU L3 缓存（通常为几十 MB）时，大内存复制会使 CPU 缓存频繁失效（Cache Miss），增加总耗时。
• 垃圾回收（GC）与生命周期管理：新列表对象的诞生意味着 Python 运行时需要追踪其引用计数并在不使用时清理，增加了运行时代价。

特殊场景：带 key 参数与预排序数据的表现

大数据量下的比较不仅限于纯数值比较，以下两种特殊场景需要格外注意：

1. 带有自定义 key 参数时

当使用 key=func（例如按对象的某个属性或复杂的 lambda 表达式排序）时，Python 会采用“装饰-排序-去装饰（Decorate-Sort-Undecorate）”的内部优化机制：先对列表每个元素调用一次 key 函数并缓存其键值。在大数据量下，如果 key 涉及 Python 层面的函数调用，计算 key 的时间往往占据了总耗时的 70% 以上。此时 sort() 与 sorted() 的相对耗时差距会被稀释到 5%~10% 左右，但 sort() 依然凭借更低的内存压力保持全面领先。

2. 局部有序或完全有序数据

Timsort 是针对真实业务数据设计的自适应排序算法。当数据已经处于有序状态（或倒序状态）时，算法只需一次完整的线性扫描（O(N) 比较），无需执行归并操作。在此场景下，因为排序本身仅耗时几毫秒，sorted() 的内存分配和拷贝耗时反倒成了最主要的开销。在完全有序的千万级列表上，list.sort() 甚至可以比 sorted() 快上 2 到 3 倍。

工程选型指南与避坑建议

生产环境选型建议总结

1. 数据量超过 10 万且输入本身是列表：如果不需要保留排序前的原始顺序，一律首选 list.sort()。这不仅能节约将近 25% 的处理时间，还能避免内存翻倍带来的潜在 OOM（内存溢出）隐患。
2. 函数式编程与不可变管道：若在链式调用、函数参数传递或并发读取场景中需要避免副作用，使用 sorted() 更加安全清晰，但需在架构设计中为这部分额外的指针内存预留足够余量。
3. 非列表数据结构：对于字典键值、集合或元组，sorted() 是开箱即用且高效的选择，无需手动先做 list(iterable) 再调用 sort()，因为 sorted() 的 C 语言底层已经完成了这一转换。