Изменения

Обрабатывая блок, каждому элементу <tex>x</tex> в этом блоке внутри этого блока взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex> так, чтобы их значения находились в промежутке <tex>\{1,2,\dots,2m\}</tex>. Очередь <tex>B</tex> будет работать непосредственно с ключами элементов.

Определим ключи элементов так, чтобы их значения были в промежутке <tex>\{1,2,\dots,2m\}</tex>. Работая с блоком <tex>C_j</tex>, будем сливать элементы, ключи которых находятся в очереди <tex>B</tex>, с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>. Как было замечено ранее, элементы, чьи ключи находятся в <tex>B</tex>, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]] за <tex>O(m)</tex>.

В итоге, получим отсортированный список <tex>\mathtt{merged}</tex>. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливо утверждениесправедливы утверждения, что <tex>\mathtt{elt}(x)=\mathtt{merged}[x]</tex> и <tex>(\pi_{i}<\pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})<\mathtt{key}(\pi_{k}))</tex>, где <tex>\pi_{i},\pi_{k}\in \mathtt{merged}</tex>, поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов.

Простым проходом по отсортированному блоку <tex>C_j^s</tex> находим последовательность ключей , соответствующую его элементам. Действуя на эту последовательность перестановкой <tex>\xixi_j</tex>, получаем последовательность ключей в порядке исходного блока.

После тогоОставшиеся ключи, как мы определили новые ключи для которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов, обновляем ключи в обрабатываемом блоке будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами.

* Вставляем в <tex>B</tex> новые ключи элементов списка <tex>\mathtt{elems}</tex>.