CPython 中实际的"sorted"方法在哪里实现，它在这里做什么？

Question

查看GitHub上CPython的源代码，我在这里看到了方法:
https://github.com/python/cpython/blob/main/Python/bltinmodule.c

更具体地说:

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;
}

我不是C语言大师，但我没有看到任何已知排序算法的实现，更不用说Python使用的特殊排序了(我想它叫Timsort?-纠正我，如果我错了)

如果你能帮我"消化"一下，我将非常感激。并理解它，因为到目前为止，我已经得到:

PyObject *newlist, *v, *seq, *callable;

这是创建一个新的列表-即使列表是可变的吗?那为什么要创建一个新的呢?
和创建一些其他指针，不知道为什么…

然后我们按照注释的建议解压缩其余的参数，如果它与那里的参数不匹配(例如作为函数'sorted')，那么我们爆发…

我很确定我读错了，所以我停在这里…

感谢先进的帮助，抱歉为多个问题，但这段代码是吹我的头脑和学习阅读这将帮助我很多!

Answer 1

实际排序由list.sort完成。sorted只是根据给定的可迭代参数创建一个新列表，对该列表进行就地排序，然后返回它。sorted的纯Python实现可能看起来像

def sorted(itr, *, key=None):
newlist = list(itr)
newlist.sort(key=key)
return newlist

大多数C代码只是用于处理底层C数据结构，检测和传播错误以及进行内存管理的样板。

实际的排序算法分布在Objects/listobject.c中;从这里开始。如果你真的对算法是什么感兴趣，而不是它在C中是如何实现的，你可能想从https://github.com/python/cpython/blob/main/Objects/listsort.txt开始。

Answer 2

列表排序实现不存在。这是一个从那里获取PyId_sort的包装函数:

callable = _PyObject_GetAttrId(newlist, &PyId_sort);

object.h包含一个宏，使用标记粘贴来定义PyId_xxx对象

#define _Py_IDENTIFIER(varname) _Py_static_string(PyId_##varname, #varname)

…从那以后我就不再挖掘了为了在整个python代码库中执行一致的命名，可能会涉及更多的宏魔术。

实现在这里:

https://github.com/python/cpython/blob/main/Objects/listobject.c

更准确地说是在第2240行

static PyObject *
list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
/*[clinic end generated code: output=57b9f9c5e23fbe42 input=cb56cd179a713060]*/
{

评论写道:

/* An adaptive, stable, natural mergesort.  See listsort.txt.
* Returns Py_None on success, NULL on error.  Even in case of error, the
* list will be some permutation of its input state (nothing is lost or
* duplicated).
*/

现在要理解算法的细节需要一些努力，但它在那里。