Powersort 是一种自适应的归并排序方法,能够为有序子序列(称为有序段)选择高效的归并顺序。它由 J. Ian Munro 和 Sebastian Wild 于 2018 年提出,利用相邻有序段的位置和长度,以很低的调度开销构造近乎最优的归并树。它的主要贡献是一种归并策略,即决定何时归并哪些相邻有序段的规则。结合适当的有序段检测和稳定归并操作,它就构成了一种能够利用输入中已有顺序的稳定排序算法。
有序段与归并顺序问题
自然归并排序首先识别输入中已有序的部分。例如,一个数组可能由几个长度相差悬殊的升序段组成。也可以检测降序段并将其反转,但必须妥善处理相等元素,以保持稳定性。
找到有序段后,算法必须决定如何将它们归并。这一选择很重要,因为一个元素所在的有序段在接连参与归并时,该元素可能会被反复复制或比较。
在标准的抽象成本模型中,归并长度为 和 的有序段,成本为 。考虑三个连续的有序段,其长度分别为 、 和 :
- 先归并前两个有序段,再将结果与第三个有序段归并,成本为 。
- 先归并后两个有序段,再将结果与第一个有序段归并,成本为 。
这两种调度方案得到的排序结果相同,但第一种的归并总工作量更小。
在通常对连续有序段进行稳定归并的框架中,只能归并相邻的有序段。因此,归并调度方案对应一棵保序二叉树:它的叶节点按原始的从左到右顺序表示各个原始有序段。如果有序段 的长度为 ,所在深度为 ,则归并总成本为
因此,调度问题就是构造一棵成本较低的有序二叉树,使权重较大的叶节点倾向于处在较浅的深度。
这与霍夫曼编码相似,但普通霍夫曼编码并不保持指定的叶节点顺序。因此,不考虑位置、直接归并最短的两个有序段,并不能作为有效的替代方法。
节点幂
Powersort 为相邻有序段之间的每个边界赋予一个较小的整数,称为节点幂。在概念上对整个输入区间进行均衡细分时,这个整数表示两个有序段在哪一层被分开。
设输入长度为 ,两个相邻有序段占据的半开区间为
它们的归一化中点为
它们之间边界的幂是满足下式的最小非负整数 :
由于两个中点都位于 内,首次分离发生在 时。
从几何上看,将区间 反复二等分。节点幂就是两个中点首次落入不同小区间时的细分层数:
- 较小的幂表示输入中较高层级的划分。
- 较大的幂表示更局部的划分,通常应当更早处理。
等价地,节点幂标识了两个中点的二进制展开中首次出现差异的位置;上述基于向下取整的定义可以精确处理落在细分边界上的情况。
节点幂根据原始的相邻有序段计算,而不是在归并后根据当时形成的更大有序段反复重新计算。实现时可以使用整数运算和位运算,无须以浮点数计算中点。
基于栈的调度
Powersort 从左到右处理有序段,同时用一个栈维护待处理的有序段及其边界幂。
从概念上说,其调度过程如下:
- 识别下一个有序段。
- 计算它与前一个原始有序段之间的边界幂。
- 归并那些边界幂大于新边界幂的待处理组。
- 保留新边界,继续扫描。
- 处理完最后一个有序段后,归并剩余的待处理组。
新遇到的低幂边界意味着一个较高层级的划分。因此,在保留这一边界以供后续处理之前,必须先完成它左侧更局部的归并。
由此得到的调度方案对应一棵以边界幂为依据的笛卡尔树,其中较小的幂更靠近根节点。这就把简单的栈操作过程与预期的层次化归并树联系起来。
对于长度分别为 、 和 的有序段,其归一化中点分别为 、 和 。两个边界的幂分别为 和 。遇到第二个幂更小的边界时,算法会先归并前两个有序段,再将合并后的有序段与最后一个有序段归并。
栈中的幂保持递增这一不变量,使待处理条目数的上界为 。除计算节点幂的成本外,调度所需的工作量与有序段数量呈线性关系。
自适应性与复杂度
Powersort 不仅适应输入的总规模,也适应有序段长度的分布。
对于长度分别为 的 个有序段,定义
这里, 是有序段长度分布的信息熵。它衡量输入分散在各个有序段中的程度:各段长度相等时,;而当一个有序段占据绝大部分输入、其余几个段都很短时,熵可能低得多。
在二路归并成本模型中, 是任何归并树的加权路径长度的下界,即使不要求保持叶节点顺序也不例外。Powersort 的归并成本满足
因此,它的归并成本与最优保序归并成本之差不超过一个线性项。“近乎最优”指的就是这一保证,并不意味着 Powersort 总能选出成本严格最小的树。
如果有序段检测采用线性时间算法,归并采用普通的线性时间算法,则其时间复杂度为
这意味着当 时,复杂度为 ,而最坏情况下仍具有通常的 上界。对于已经有序的输入,可以在线性时间内完成识别,无须执行归并。
调度栈需要 的辅助空间。这与归并操作本身所需的内存是分开的:传统的基于数组的稳定实现,总体上可能需要 的临时存储空间。调度栈很小,并不意味着整个排序算法是原地算法。
与蒂姆排序的关系
Powersort 与蒂姆排序采用了相同的实用思路:
- 检测已有的有序段。
- 在有益时扩展过短的有序段,通常使用插入排序。
- 以稳定方式归并相邻有序段。
- 使用高效的归并例程,其中可能包括疾驰搜索。
两者的核心区别在于归并策略。经典蒂姆排序根据涉及待处理有序段长度的不等式来决定何时归并。Powersort 则使用由有序段位置和长度推导出的边界幂。
由于这种职责分离,可以用 Powersort 的调度方式替换蒂姆排序的归并顺序规则,而无须替换外围的有序段检测、比较处理、临时缓冲区管理或归并机制。
在 CPython 3.11 中,Python编程语言的 list.sort() 和 sorted() 底层实现采用了 Powersort 的归并策略。这一变化针对的是内部调度策略,并未改变公开的排序接口或稳定性保证。因此,将 Python 的排序实现称为蒂姆排序时,也可能是在指一种更广义的实现,其归并调度使用的是 Powersort。
适用范围与局限
Powersort 的数学保证针对的是一种特定成本模型。实际运行时间还取决于元素比较成本、数据移动、分支行为、CPU 缓存效应以及归并实现的细节。
例如,归并长度为 和 的有序段,并不一定恰好进行 次比较。普通归并最多进行 次比较,而疾驰搜索或其他捷径在适宜的数据上可以大幅减少比较次数。因此,最小化抽象归并成本,并不一定能在每种输入上都使比较次数或运行时间最少。
这一保证也只适用于提供给归并策略的那些有序段。扩展短有序段会改变有序段序列,因此在分析完整排序实现时,必须计入扩展操作的成本。
最后,Powersort 是最优保序归并的一种近似方法,而不是精确优化算法。精确方法可以构造成本最低的有序归并树,但需要更复杂的调度机制。Powersort 放弃了精确最优性,换取了一套简洁、从左到右运行且开销较低的过程,同时保证额外归并成本具有线性上界。