Timsort

定义

Timsort 是 Tim Peters 于 2002 年为 Python 设计的混合排序算法,融合归并排序与二分插入排序,并针对真实数据中常见的局部有序片段做了大量优化。

原理

算法扫描数组识别天然有序的连续片段(run),过短的 run 用插入排序扩展到最小长度;随后将各 run 压栈,依据栈内长度不变式选择时机归并,保证归并平衡。还引入 galloping(飞奔)模式,在一侧连续获胜时用指数搜索批量拷贝元素。最坏复杂度 O(n log n),对已基本有序的数据接近 O(n),且排序稳定。

应用

CPython 的 list.sort 与 sorted、Java 的对象数组排序(Arrays.sort 对象版本)、Android 平台及 V8 引擎的 Array.prototype.sort 均采用 Timsort 或其变体。

说明

2015 年研究者用形式化验证发现其栈不变式实现存在边界缺陷,随后各运行时进行了修正,成为软件验证的知名案例。