CPython中sorted方法实际实现位置及builtin_sorted代码解析咨询

先贴出你看到的builtin_sorted代码：

static PyObject *
builtin_sorted(PyObject *self, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
    PyObject *newlist, *v, *seq, *callable;

    /* Keyword arguments are passed through list.sort() which will check
       them. */
    if (!_PyArg_UnpackStack(args, nargs, "sorted", 1, 1, &seq))
        return NULL;

    newlist = PySequence_List(seq);
    if (newlist == NULL)
        return NULL;

    callable = _PyObject_GetAttrId(newlist, &PyId_sort);
    if (callable == NULL) {
        Py_DECREF(newlist);
        return NULL;
    }

    assert(nargs >= 1);
    v = _PyObject_FastCallKeywords(callable, args + 1, nargs - 1, kwnames);
    Py_DECREF(callable);
    if (v == NULL) {
        Py_DECREF(newlist);
        return NULL;
    }
    Py_DECREF(v);
    return newlist;
}

一、代码逐行解析 #

1. 参数拆解逻辑 #

_PyArg_UnpackStack是CPython用于解析函数参数的底层宏，这里的作用是：

• 明确sorted需要且仅需要1个必选参数（待排序的序列seq），所以参数数量范围设为1, 1。
• 如果参数不符合要求（比如没传序列、传了多个位置参数），直接返回NULL触发Python层面的参数错误异常。

2. 创建新列表的原因 #

PySequence_List(seq)会把输入的任意序列（元组、字符串、自定义序列等）转换成全新的列表对象，这么做的核心原因是：

• sorted()的设计目标是返回排序后的新列表，完全不修改原输入序列；而list.sort()是原地修改列表的方法，无返回值。
• 通过复制原序列为新列表，后续对新列表执行原地排序，既复用了list.sort()的成熟实现，又保证原序列不受影响，符合Python开发者对sorted()的行为预期。

3. 获取并调用sort方法 #

• _PyObject_GetAttrId(newlist, &PyId_sort)：拿到新列表的sort方法对象，等价于Python代码里的newlist.sort。
• _PyObject_FastCallKeywords(callable, args + 1, nargs - 1, kwnames)：把sorted调用时传入的额外参数（比如key=xxx、reverse=True）传递给sort方法执行。这里args + 1是跳过已经处理的第一个序列参数，只把剩下的参数传给sort——因为sort的参数和sorted除了第一个序列参数外完全一致。

4. 引用计数清理 #

CPython的C API需要手动管理对象引用计数：

• 调用完sort方法后，释放callable（即sort方法对象）的引用。
• sort方法返回None（Python里list.sort()无返回值），所以拿到返回值v后也要释放它的引用。
• 如果中间任何步骤出错，会释放newlist的引用并返回NULL，避免内存泄漏。

二、Timsort的实际实现位置 #

builtin_sorted只是一个包装函数，本身不实现排序算法，它的核心逻辑是复用list.sort()的实现。而Python的Timsort算法实际在这两个位置：

1. list.sort()的入口实现位于Objects/listobject.c的list_sort函数，负责处理列表排序的前置检查、参数解析等逻辑。
2. Timsort的核心算法（包括归并、分区、galloping搜索等）实现位于Python/timsort.c文件中，这部分是排序的底层核心代码。

内容的提问来源于stack exchange，提问作者0Interest