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