Изменения

Теперь рассмотрим проблему упаковки, которую решим следующим образом. Будем считать что число бит в контейнере <tex>logm >= logloglogn</tex>, потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/loglogn</tex> хэшированных значений (сегментов) в себе на уровне <tex>logh</tex> в Э.П.дереве. Полное число хэшированных бит в контейнере <tex>(2logn)(cloglogn)</tex> бит. Хотя хэшированны биты в контейнере выглядят как <tex>0^{i}t_{1}0^{i}t_{2}...t_{h/loglogn}</tex>, где <tex>t_{k}</tex>-ые это хэшированные биты, а нули это просто нули. Сначала упаковываем loglogn контейнеров в один и получаем <tex>w_{1} = 0^{j}t_{1, 1}t_{2, 1}...t_{loglogn, 1}0^{j}t_{1, 2}...t_{loglogn, h/loglogn}</tex> где <tex>t_{i, k}</tex>: <tex>k = 1, 2, ..., h/loglogn</tex> из <tex>i</tex>-ого контейнера. мы ипользуем <tex>O(loglogn)</tex> шагов, чтбы упаковать <tex>w_{1}</tex> в <tex>w_{2} = 0^{jh/loglogn}t_{1, 1}t_{2, 1} ... t_{loglogn, 1}t_{1, 2}t_{2, 2} ... t_{1, h/loglogn}t_{2, h/loglogn} ... t_{loglogn, h/loglogn}</tex>. Теперь упакованные хэш биты занимают <tex>2logn/c</tex> бит. Мы используем <tex>O(loglogn)</tex> временичтобы распаковать <tex>w_{2}</tex> в <tex>loglogn</tex> контейнеров <tex>w_{3, k} = 0^{jh/loglogn}0^{r}t_{k, 1}O^{r}t_{k, 2} ... t_{k, h/loglogn} k = 1, 2, ..., loglogn</tex>. Затем используя <tex>O(loglogn)</tex> времени упаковываем эти <tex>loglogn</tex> контейнеров в один <tex>w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} ... t_{1, h/loglogn}0^{r}t_{2, 1} ... t_{loglogn, h/loglogn}</tex>. Затем используя <tex>O(loglogn)</tex> шагов упаковать <tex>w_{4}</tex> в <tex>w_{5} = 0^{s}t_{1, 1}t_{1, 2} ... t_{1, h/loglogn}t_{2, 1}t_{2, 2} ... t_{loglogn, h/loglogn}</tex>. В итоге мы используем <tex>O(loglogn)</tex> времени для упаковки <tex>loglogn</tex> контейнеров. Считаем что время потраченное на одно слово {{---}} константа. ==Вывод==Таким образом имеем:{{Теорема|id=th1. |statement=<tex>n</tex> целых чисел могут быть отсортированы за время <tex>O(nloglogn)</tex> и линейную память.}}