当合并运行A，B时（在函数merge_lo中），它说“也必须有那个ssa.keys[na-1]属于合并的末尾”。为什么？

Question

A和B是堆栈上的相邻运行，A是底部和较小的运行（如果B较小，merge\u hi将执行合并，但同样的问题也适用于那里）。我一直在试图找出为什么A的最后一个元素必须大于B的最后一个元素，因为我不知道运行分解（或算法的其余部分）如何确保这种条件。同样，在同一个函数中，代码似乎表明B的第一个元素总是小于A的第一个元素，我也不明白为什么，但我猜这个问题的答案与第一个问题的答案有关。

Answer 1

总之，奔腾是原因。这就是为什么我们一开始没有看到它，因为我认为gallop_{code>left，right}仅从合并中调用。但这不是真的<代码>gallop_。。。也从处的merge\u调用，在merge之前，调用{code>hi}，以查找“b在a中从哪里开始？”还有“a在哪里以b结尾？”。这些调用（和后续代码）更改ssb（及其长度nb），以及ssa及其长度na，从而满足标题中的不变量。

也就是说，重点是A和B不是要排序的原始列表中的“runstack上的相邻运行”。在调用{code>合并{code>低，高}之前，对它们进行修剪，使标题中的条件保持不变。也就是说，在A与B合并之前，明确不考虑B中大于A最后一个元素的元素。换言之，“还必须具有ssa。键[na-1]属于合并的末尾”是真的，这并不是因为ssa的某些特殊属性。键[na-1]，但因为我们以这样的方式定义了“合并结束”。：-）

这也意味着，当您自己实现Timsort时，您必须忽略奔腾，也必须忽略这里讨论的优化，否则代码将无法正常工作。