问Timsort合并模式

EN

我想了解提姆塞德。包括所有细节，所以像“在Java或Python中调用.sort()”这样的回答不是我想要的。

我已经阅读了这些来源提到的维基百科文章、Java实现、CPython实现、listsort.txt，以及listsort.txt references：近乎最优的Mergesorts:最适合现有运行的快速实用的排序方法的出版物。我还略读了一些近乎最佳的Mergesorts的参考文献，即几何问题的标度及相关技术、统一看待数据结构和求最近公共祖先的快速算法；我不会说我完全理解后三种，但我确信它们不会回答我的问题。

我摸索大多数子算法:运行计数和反向运行，二进制插入排序，合并(保存头/尾部分)，奔腾。请不要试图解释这些，我知道什么，怎么做，以及为什么要这样做。

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

文件listsort.txt声明(第346行)：

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

我理解芒罗和怀尔德的力量排序是如何运作的，我发现他们对“近乎最佳的字母树”和“二分法”和“沿笛卡尔树边缘的移动”的解释已经足够了。

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

显然，它们是不同的：

• powersort考虑节点的权限，而Timsort则考虑运行长度，
• powersort有一个不变式:B <= A，而Timsort有两个:y>X和Z>Y+X(其中X是最近的读取运行，它在数组中具有最高的起始索引，它位于或将放在堆栈的顶部，而A是运行Y和X之间的节点)，
• 幂排序总是合并Y和X，而Tim排序合并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异常；但是我在代码中没有发现类似的情况。