当merging在Timsort中运行A、B时(在函数merge_lo中)，它会说“还必须让ssa.keys[na-1]属于merge的末尾”。为什么？

Question

A和B是堆栈上相邻的运行，A是最小的运行(如果B更小，merge_hi将执行合并，但同样的问题也适用于那里).I一直试图弄清楚为什么A的最后一个元素必须大于B的最后一个元素，因为我不明白运行分解(或算法的其余部分)如何确保这种条件。此外，在同一函数中，代码似乎表明B的第一个元素总是小于A的第一个元素，我也不明白为什么，但我猜这个问题的答案与第一个问题的答案有关。

Answer 1

简而言之，飞驰就是原因。这就是为什么我们一开始没有看到它的原因，因为我认为gallop_{left，right}只能从merge_{lo，hi}调用。但这不是真的。gallop_...在merge_{lo，hi}被调用之前，也会从merge_at中调用，以便找到“b在a中从哪里开始？”和“a在b中的结尾在哪里？”。这些调用(以及随后的代码)更改了ssb (及其长度nb)，还更改了ssa及其长度na，以便满足标题中的不变量。

也就是说，重点是A和B不是在要排序的原始列表中找到的“相邻运行在运行栈上”( the runstack)。在调用merge_{lo，hi}之前，会对它们进行修剪，以便标题中的条件成立。也就是说，在A与B合并之前，B的元素大于A的最后一个元素的元素被排除在explicitly之外。换句话说，“还必须让ssa.keys[na-1]属于合并的结尾”是真的，不是因为ssa.keys[na-1]的一些特殊属性，而是因为我们以这种方式定义了“合并的结尾”。:-)

这也意味着，当你自己实现Timsort的时候，如果你忽略了飞驰，你也必须忽略这里所讨论的优化，否则代码将不能正常工作。