Когда объединение запускает A, B в Timsort (в функции merge_lo), оно говорит: «Должно быть, ssa.keys [na-1] принадлежит в конце объединения».Зачем?

Question

A и B являются смежными сериями в стеке, где A - нижний и меньший циклы (если бы B был меньше, merge_hi выполнял бы объединение, но тот же вопрос применим и там). Я пытался выяснить, почему последний элемент A ДОЛЖЕН быть больше, чем последний элемент B, потому что я не вижу, как декомпозиция выполнения (или остальная часть алгоритма) могла бы обеспечить это условие. Кроме того, в той же функции код, кажется, предполагает, что первый элемент B всегда меньше, чем первый элемент A, что я также не понимаю почему, но я предполагаю, что ответ на этот вопрос связан с ответом первого вопроса.

Answer 1

Короче, галопом является причина. Вот почему мы сначала его не видели, потому что я думал, что gallop_ {left, right} вызывается только из merge _ {lo, hi}. Но это не правда. gallop_ ... также вызываются из merge_at, до вызова merge _ {lo, hi}, чтобы найти "С чего начинается b в a?" и "Где кончается б?" Эти вызовы (и последующий код) изменяют ssb (и его длину nb), а также ssa и его длину na, так что выполняется инвариант в заголовке.

То есть, дело в том, что A и B являются , а не"смежными трассами в стеке выполнения", как было найдено в исходном списке для сортировки. Перед вызовом merge _ {lo, hi} они обрезаются, так что условие в заголовке выполняется. То есть до слияния A с B элементы B, превышающие последний элемент A, явно не учитываются. Другими словами, «Должно также быть, что ssa.keys[na-1] принадлежит в конце слияния», верно не из-за какого-то особого свойства ssa.keys[na-1], а потому, что мы определили «конец слияния» таким образом. : -)

Это также означает, что когда вы внедряете Timsort самостоятельно и не учитываете скачки, вы также должны не учитывать эту оптимизацию, о которой здесь говорится, иначе код не будет работать правильно.