Timsort 的合并模式

Question

我想了解 Timsort。包括所有细节，所以像“只需在 Java 或 Python 中调用”这样的答案.sort()不是我想要的。

我已经阅读了Wikipedia 文章、Java 实现、CPython 实现、这些来源提到的listsort.txt以及出版物 listsort.txt 参考资料：近乎最优的合并排序：最佳地适应现有运行的快速、实用的排序方法。我还浏览了近乎最优归并排序的一些参考资料，即几何问题的缩放和相关技术、数据结构的统一视图以及查找最近共同祖先的快速算法；我不会说我完全理解后三个，但我很确定他们没有回答我的问题。

我了解大多数子算法：运行计数、反转运行、二进制插入排序、合并（保存头/尾部分）、驰骋。请不要试图解释这些，我知道它们是什么、如何以及为什么。

我怀念的是合并模式。实际上，我通过维护运行堆栈并根据反复检查不变量来决定何时合并来了解它的工作原理；我还看到目标是：适应自然运行、实现排序稳定性、平衡合并、利用时间局部性并保持算法简单。但我不明白为什么重新建立这些不变量会产生有效的算法。

文件 listsort.txt 指出（第 346 行）：

该代码现在使用“powersort”合并策略：“近乎最优的合并排序：快速、实用的排序方法，最佳地适应现有运行”J. Ian Munro 和 Sebastian Wild

我理解 Munro 和 Wild 的 powersort 是如何工作的，并且我发现他们的解释涉及“近乎最优的字母树”和“二分启发式”和“沿着笛卡尔树边缘的移动”就足够了。

我无法理解 powersort 和 Timsort 合并模式之间的联系。

显然，它们是不同的：

• powersort 考虑节点功率，而 Timsort 考虑游程长度，
• powersort 有一个不变量：B <= A，而 Timsort 有两个：Y > X 和 Z > Y + X（其中 X 是最近读取的运行，它在数组中具有最高的起始索引，并且位于顶部或将放置在堆栈的顶部，A 是运行 Y 和 X 之间的节点），
• powersort 始终合并 Y 和 X，而 Timsort 合并 Y 和 X 或 Z 和 Y。

我发现较高的节点功率通常出现在较短的运行之间，但我无法从一种算法中推断出另一种算法。请解释一下这两者之间有什么联系。

一旦我理解了这一点，我希望我也能找到堆栈容量的合理性：

    /*
     * Allocate runs-to-be-merged stack (which cannot be expanded).  The
     * stack length requirements are described in listsort.txt.  The C
     * version always uses the same stack length (85), but this was
     * measured to be too expensive when sorting "mid-sized" arrays (e.g.,
     * 100 elements) in Java.  Therefore, we use smaller (but sufficiently
     * large) stack lengths for smaller arrays.  The "magic numbers" in the
     * computation below must be changed if MIN_MERGE is decreased.  See
     * the MIN_MERGE declaration above for more information.
     */
    int stackLen = (len <    120  ?  5 :
                    len <   1542  ? 10 :
                    len < 119151  ? 19 : 40);

这些数字是如何计算的？为什么可以肯定堆栈不会增长到超出这些范围？为什么代码不检查是否有空闲插槽？如果没有，那么（a）扩展堆栈或（b）在顶部合并将很容易防止 ArrayOutOfBounds 异常；但我在代码中没有找到类似的东西。

Answer 1

\n

请解释一下这两者之间有什么联系。

\n

\n

他们实例化了一个通用框架：将输入列表拆分为多个运行，合并相邻的运行，直到只剩下一个。执行此操作的不同方法可以用二叉树来概括，二叉树的叶子是游程。Timsort、powersort 和 peeksort（来自与 powersort 相同的论文）代表了三种不同的树构建方法。

\n

\n

这些数字是如何计算的？

\n

\n

错了。（如果链接失效，那就是 de Gouw、Rot、de Boer、Bubel 和 H\xc3\xa4hnle：“OpenJDK 的 java.utils.Collection.sort() 已损坏：好的，坏的以及最坏的情况”。）

\n