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