81
правка
Изменения
Нет описания правки
Данный алгоритм базируется на следующей лемме:
{{ЛеммаЛемма1
|id=lemma1.
|statement=
==Сортировка на маленьких целых==
Для лучшего понимания действия алгоритма и материала, изложенного в данной статье, в целом, ниже представлены несколько полезных лемм.
{{ЛеммаЛемма2
|id=lemma2.
|statement=
|proof=
}}
{{ЛеммаЛемма3
|id=lemma3.
|statement=
Так как мы можем делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, мы можем упаковать медианы из первого, второго, ..., <tex>g</tex>-о чисел из 5 контейнеров в один контейнер за константное время. Таким образом набор <tex>S</tex> из медиан теперь содержится в <tex>n/(5g)</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex> уберем хотя бы <tex>n/4</tex> чисел среди <tex>n</tex>. Затем упакуем оставшиеся из <tex>n/g</tex> контейнеров в <tex>3n/4g</tex> контейнеров и затем продолжим рекурсию.
}}
{{ЛеммаЛемма4
|id=lemma4.
|statement=
Если <tex>g</tex> целых чисел, в сумме использующие <tex>(logn)/2</tex> бит, упакованы в один контейнер, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы за время <tex>O((n/g)logg)</tex>, с использованием <tex>O(n/g)</tex> места.
|proof=
Так как используется только <tex>(logn)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, мы можем использовать bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает <tex>O(n/g)</tex> времени и места. Потому, что мы используем <tex>(logn)/2</tex> бит на контейнер нам понадобится <tex>sqrt {n}</tex>
}}
