47
правок
Изменения
м
→Основная идея
* {{Acronym|Достаем из очереди ключи|если это первый блок — ничего не делаем}} и конвертируем их в элементы <tex>\pi</tex>.
* Классический [[Сортировка слиянием#Принцип работы#Слияние двух массивов | merge]] только что полученных элементов <tex>\pi</tex> с элементами нового блока, но с модификацией: генерируются 2 дополнительных массива - индексы элементов исходных массивов в новом. Слияние массивов назовем <tex>\mathtt{merged}</tex>.
* На массив индексов, относящиеся к новому блоку, действует перестановка смещений сортированного варианта этого блока. Таким образом мы добиваемся эквиваленции отношений {{Acronym|ключей|смещений}} к отношениям элементов в очереди и элементов в блоке, а ключи находятся в диапазоне <tex>O(m)</tex>.
* Первый массив индексов, который соответствует элементам, ранее находящимся в очереди, вновь кладутся в очередь (обычными <tex>\mathrm{insert}</tex>-ами). Второй массив обрабатывается описанным выше алгоритмом <tex>\mathrm{LIS}</tex>, при том массив <tex>\mathtt{predecessor}</tex> строится из ключей с помощью <tex>\mathtt{merged}</tex>.
==== Визуализация ====
