CPython/list.sort / sorted

让列表排序利用输入中已有的顺序

CPython 的列表排序识别已有序段，补齐短段，再按 Powersort 策略稳定归并，兼顾局部有序输入与通用排序。

v3.13.0检索与计算核验 2026-10-09

工程问题#

Python 列表可能已部分有序，而且对象比较可以比搬动指针昂贵；通用排序需要保持同键元素的原有顺序，并减少不必要的比较。

实际实现#

list_sort_impl 从左到右识别自然 run，短 run 用二分插入排序扩展到 minrun；found_new_run 计算相邻 run 的 power，决定待处理栈中哪些相邻段先归并，最后合并剩余段。

处理流程#

扫描并整理已有序的自然 run
用二分插入排序补齐过短的 run
按 Powersort 的 power 维护相邻 run 的合并次序
稳定归并，直到只剩完整有序段

源码片段#

固定版本 · 原文摘录

Objects/listobject.cv3.13.0 · L3038–L3054

查看原文件

3038        /* Identify next run. */3039        n = count_run(&ms, &lo, nremaining);3040        if (n < 0)3041            goto fail;3042        /* If short, extend to min(minrun, nremaining). */3043        if (n < minrun) {3044            const Py_ssize_t force = nremaining <= minrun ?3045                              nremaining : minrun;3046            if (binarysort(&ms, &lo, force, n) < 0)3047                goto fail;3048            n = force;3049        }3050        /* Maybe merge pending runs. */3051        assert(ms.n == 0 || ms.pending[ms.n -1].base.keys +3052                            ms.pending[ms.n-1].len == lo.keys);3053        if (found_new_run(&ms, n) < 0)3054            goto fail;

list_sort_impl

先识别自然 run，再以 binarysort 扩展短段；随后交由 found_new_run 决定是否归并待处理段。调用名中的 binary 指二分定位插入位置，并不消除数组移动成本。

CPSF License Version 2，并保留历史许可声明

Objects/listobject.cv3.13.0 · L2605–L2623

查看原文件

2605static int2606found_new_run(MergeState *ms, Py_ssize_t n2)2607{2608    assert(ms);2609    if (ms->n) {2610        assert(ms->n > 0);2611        struct s_slice *p = ms->pending;2612        Py_ssize_t s1 = p[ms->n - 1].base.keys - ms->basekeys; /* start index */2613        Py_ssize_t n1 = p[ms->n - 1].len;2614        int power = powerloop(s1, n1, n2, ms->listlen);2615        while (ms->n > 1 && p[ms->n - 2].power > power) {2616            if (merge_at(ms, ms->n - 2) < 0)2617                return -1;2618        }2619        assert(ms->n < 2 || p[ms->n - 2].power < power);2620        p[ms->n - 1].power = power;2621    }2622    return 0;2623}

found_new_run

计算相邻 run 在概念合并树中的 power，并归并栈中 power 更大的相邻段。这是该版本的 Powersort 合并调度，不是早期 Timsort 的长度规则。

CPSF License Version 2，并保留历史许可声明

两个片段分别展示短段整理与归并次序；完整稳定归并、galloping 和比较器处理见同一源文件。

收益与取舍#

工程分析

带来的收益

复用输入已有的顺序，减少许多部分有序输入的比较工作
保持排序稳定性，适合多字段分步排序

付出的代价

归并可能需要线性规模的临时指针存储，key 函数还会带来键数组等成本
二分插入只减少比较次数；移动元素在一般情况下仍可达平方量级，因此这里只用于短 run

可比较的选择

原地堆排序可减少归并临时空间并提供最坏 O(n log n)，但通常不稳定，也不利用自然 run。

版本与适用范围#

对应 CPython v3.13.0 的 list.sort 实现。它延续 Timsort 的自适应稳定归并框架，但 run 的合并次序已使用 Powersort；不应照搬早期 Timsort 栈长不变量。

参考来源#

源码、官方文档与原始论文

cpython · list_sort_impl / found_new_run

Objects/listobject.c · list_sort_impl / found_new_run

源码v3.13.0

CPython · listsort 算法设计说明

Objects/listsort.txt · Powersort merge strategy