Изменения

предположимПредположим, что каждый контейнер содержит <tex>\log m \log\log n > \log n</tex> бит, что <tex>g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>(\log n)/(2g)</tex> бит, и что <tex>g</tex> маркеров упакованы в один контейнер тем же образом что и числа, тогда . Тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(n/g)</tex>, с использованием <tex>O(n/g)</tex> памяти.

Заметим, что несмотря на то, что длина контейнера <tex>\log m \log\log n</tex> бит , всего <tex>\log m</tex> бит используется для хранения упакованных чисел. Так же как в '''леммах №4, №5''' сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел , помещаем <tex>g \log\log n</tex> вместо <tex>g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей <tex>g \log\log n</tex> контейнеров, упаковываем <tex>g \log\log n</tex> контейнеров в <tex>g</tex>, упаковывая <tex>\log\log n</tex> контейнеров в один. Далее делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего <tex>O(g \log\log n)</tex> времени для каждой группы и <tex>O(n/g)</tex> времени для всех чисел. После завершения транспозиции, распаковываем <tex>g</tex> контейнеров в <tex>g \log\log n</tex> контейнеров.

Заметим, что если длина контейнера <tex>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g \le \log n</tex> чисел в один контейнер, тогда выбор в '''лемме №3''' может быть сделан за время и место память <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве доказательстве '''леммы №3''' теперь может быть сделана за время <tex>O(n/g)</tex>.

==ЛитераураЛитература==