Изменения

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

Так как используется только <tex>(\log n)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, используем bucket sorting sort, чтобы отсортировать все контейнеры. , представляя каждый как число, что занимает <tex>O(n/g)</tex> времени и местапамяти. Так как используется <tex>(\log n)/2</tex> бит на контейнер, понадобится <tex>\sqrt{n}</tex> шаблонов для всех контейнеров. Затем поместим <tex>g < (\log n)/2</tex> контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более <tex>g - 1</tex> контейнеров, которые не смогут образовать группу. Поэтому не более <tex>\sqrt{n}(g - 1)</tex> контейнеров не смогут сформировать группу. Для каждой группы помещаем <tex>i</tex>-е число во всех <tex>g</tex> контейнерах в один. Таким образом берутся <tex>g</tex> <tex>g</tex>-целых векторов и получаем получаются <tex>g</tex> <tex>g</tex>-целых векторов , где <tex>i</tex>-ый вектор содержит <tex>i</tex>-ое число из входящего вектора. Эта транспозиция может быть сделана за время <tex>O(g \log g)</tex>, с использованием <tex>O(g)</tex> местапамяти. Для всех групп это занимает время <tex>O((n/g) \log g)</tex>, с использованием <tex>O(n/g)</tex> местапамяти.

Для контейнеров вне групп (которых <tex>\sqrt{n}(g - 1)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется не более <tex>O(n/g)</tex> места времени и временипамяти. После всего этого используем bucket sorting sort вновь для сортировки <tex>n</tex> контейнеров. таким Таким образом , все числа отсортированы.

Заметим, что когда <tex>g = O( \log n)</tex> , сортировка <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров произойдет за время <tex>O((n/g) \log\log n)</tex>, с использованием <tex>O(n/g) места</tex> памяти. Выгода очевидна.