76
правок
Изменения
→Деление на блоки
=== Деление на блоки===
Последовательность <tex>S</tex> делится на блоки <tex>C_j, ~j=1,~\dots,~,\lceil\frac{n}{m}\rceil</tex>, последвовательных элементов:
<tex>C_j=(\pi_{(j-1)m+1},\pi_{(j-1)m+2},~\dots~,\pi_{(j-1)m+m)})</tex>
Обозначим за <tex>C_j^s</tex> отсортированный блок <tex>C_j</tex>. Отсортированные и неотсортированные блоки будем хранить в памяти.
[[Цифровая сортировка]] каждых блоков отдельно будет давать нам время рваботы <tex>O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)</tex>. Чтобы отсортировать их за линейное время, дополним каждый элемент номером его блока и получим пары <tex>\langle\lceil i/m\rceil,\pi_i\rangle</tex>. Цифровая сортировка этих пар, если принимать за старший разряд номер блока, а за младший значение элемента, будет работать за <tex>O(n)</tex>, потому что значения элементов и номера блоков не превосходят <tex>n</tex>.
=== Обработка блока ===
Обрабатывая блоки, будем работать не со значениями элементов, а с ключами, которые определенны для каждого элемента внутри блоков. Все блоки будут обрабатываться онлайн, то есть мы не перейдём к обработке следующего блока, пока не закончим с текущим.
