看了Python源码中的排序算法,我才知道什么叫极致优化

我是被一段代码惊到才去看Python排序的。那天在调试一个性能问题，随手翻了翻list.sort()的源码。结果一看就停不下来，这帮写CPython的人，为了排序这件事简直疯了。

先说个最普通的细节。Python的排序用的是Timsort，这个算法是2002年由Tim Peters发明的。Tim Peters是谁？就是写《Python之禅》的那个人。他把归并排序和插入排序揉在一起，搞出了一个混合体。这个算法在真实数据上表现极好，因为真实数据通常有某种模式，不是完全随机的。

我最早不理解，为什么要用这么复杂的算法。看源码才知道，Python的排序不是通用的，它是针对真实数据特征做了大量专门优化的。比如数据里如果有连续的递增或递减片段，Timsort会直接识别出来当天然的有序块利用。这比傻乎乎的一路分到底快太多了。

源码里最让我吃惊的是minrun的计算。每次排序前，Python会算出一个叫minrun的值，在32到64之间。这个值用来控制归并的粒度。算minrun的方法不是随便取个中间数，它用了位运算，保证最后数组长度除以minrun约等于2的整数次幂。这样做归并的时候，每次合并的块大小差不多，效率最高。

还有那个galloping mode。普通归并排序比较两个块时，是一次比一个。但Python发现如果连续多次从同一个块取元素，说明另一个块很可能已经跟不上了。这时候它会切换到快速搜索模式，用二分查找批量移动数据。这个切换点不是固定的，源码里有个硬编码的7，连续赢7次就切换。

更绝的是，Python的排序是稳定的。稳定是什么意思？就是两个值相等的元素，排序后顺序保持不变。这听起来简单，但为了这个保证，Timsort在归并时做了特殊处理，保证不会破坏原有顺序。很多人不知道，Python的这个稳定性是写死在语言规范里的，不是实现细节。

看源码会注意到一个变量叫pending，是一个栈。排序过程中产生的每一段有序数据都压到栈里。每次压入新块时，Python会检查栈里后面几个块的长度，如果长度不满足特定条件就立刻合并。这个条件我看了很久才看懂，它保证合并后的块长度不会太长也不会太短，整体呈现一个等比数列的形状。这样做归并时内存访问很友好，缓存命中率高。

还有个小细节，Python源码里大量用了goto语句。CPython是用C写的，C语言里goto经常被骂，但排序代码里用得很克制。只在几个性能关键的路径上用，避免函数调用开销。我数了一下，整个排序函数里用了不到10个goto，每一个都有注释说明为什么要跳。

内存分配也很讲究。Timsort需要一个临时数组来归并，这个临时数组的大小不是无脑开成原数组一半，而是动态计算的。如果归并的两个块大小差距很大，会用小的那个块做临时数组。这样就避免了大量内存浪费。在嵌入式或者内存受限的环境下，这种设计很实用。

我试着模拟了几个场景。一个是完全逆序的情况，Python的排序处理得比预期快，因为它能识别出降序片段直接反转。另一个是大量重复值的情况，这时候galloping mode会疯狂触发，大幅减少比较次数。还有几乎有序的情况，Timsort几乎退化成线性扫描，很快就结束了。

有个坑是自定义排序的key函数。很多人不知道，Python对每个元素只调用一次key函数，把结果存起来。这个叫“key caching”机制。源码里有一个专门的步骤，在排序开始前先计算出所有key值，排序时直接比较缓存的结果。如果key函数很耗时，这种设计能节省大量重复计算。代价是需要额外内存存key值。

再说说异常处理。排序过程中如果key函数抛出异常，Python必须保证数据不被破坏。源码里有一个cleanup路径，异常发生时把已经部分排序的数据恢复到稳定状态。这个恢复不是全盘重置，而是利用缓存信息做逆向操作。我看这段代码时觉得这比排序本身还复杂。

还有一个细节容易被忽略：Python的列表排序不会产生额外副本。所有操作都在原列表上完成，临时数组只在外部分配。这意味着调用list.sort()后，原来的列表对象就被修改了。如果是sorted()函数，它会在排序前先复制一份，复制也有优化，用的是memcpy这样的底层内存操作。

Timsort还有一个特性叫“自适应”。它不需要任何预处理，直接读数据就能自动调整策略。数据很乱时它表现不差，数据有规律时它表现极好。这种“无假设”的设计思路很符合Python的哲学，你不需要告诉Python你的数据长什么样，它自己会判断。

最后说一个让我惊讶的地方。Python的排序代码是整个CPython里最老的部分之一，从2002年到现在20多年，修改次数很少。这意味着当初的设计就考虑得很周全。很多后来想改的人发现，改一个小地方，某个极端情况就崩了。

写代码的人要是都能学学这个思路，把算法做到极致，再交给时间去检验，那软件质量会好很多。你看，一个排序函数，你天天用，却不知道背后有这么多人想办法让它更快更稳。下次你在代码里写一行my_list.sort()的时候，想想那些被压入栈的块，那些被比较的galloping次数，那些精准计算的minrun值。这大概就是高水平程序员和普通程序员的区别吧。