81
правка
Изменения
Нет описания правки
Заметим, что несмотря на то, что длина контейнера <tex>logmloglogn</tex> бит всего <tex>logm</tex> бит используется для хранения упакованных чисел. Так же как в леммах четыре и пять мы сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел мы помещаем <tex>gloglogn</tex> вместо <tex>g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе содержащей <tex>gloglogn</tex> контейнеров мы сначала упаковываем <tex>gloglogn</tex> контейнеров в <tex>g</tex> контейнеров упаковывая <tex>loglogn</tex> контейнеров в один. Далее мы делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего <tex>O(gloglogn)</tex> времени для каждой группы и <tex>O(n/g)</tex> времени для всех чисел. После завершения транспозиции, мы далее распаковываем <tex>g</tex> контейнеров в <tex>gloglogn</tex> контейнеров.
}}
Заметим, что если длина контейнера <tex>logmloglogn</tex> и только <tex>logm</tex> бит используется для упаковки <tex>g <= logn</tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)</tex>.
