81
правка
Изменения
Нет описания правки
|id=lemma2.
|statement=
<tex>n</tex> целых чисел можно отсортировать в <tex>\sqrt{n}</tex> наборов <tex>S_{1}</tex>, <tex>S_{2}</tex>, ..., <tex>S_{\sqrt{n}}</tex> таким образом, что в каждом наборе <tex>\sqrt{n}</tex> чисел и <tex>S_{i}</tex> < <tex>S_{j}</tex> при <tex>i</tex> < <tex>j</tex>, за время <tex>O(nlog(logn)/logk)</tex> и место <tex>O(n)</tex> с не консервативным преимуществом <tex>klog(logn)</tex>
|proof=
}}
Если <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>
}}
