Изменения

'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(n\log\log n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.

Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (0<<tex>e</tex><1) Э.П.поддеревьев, в каждом из которых <tex>n^{1 - e}</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(n\log\lognlog n)</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(n\log\lognlog n)</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

Если мы сортируем целые числа из множества {0, 1, ..., <tex>m</tex> - 1} с длиной контейнера <tex>klogk \log (m + n)</tex> с <tex>k</tex> >= 1, тогда мы сортируем с неконсервативным преимуществом <tex>k</tex>.

Взяв <tex>s = 2logn2 \log n</tex> мы получим хэш функцию <tex>h_{a}</tex> которая захэширует <tex>n</tex> чисел из <tex>U</tex> в таблицу размера <tex>O(n^2)</tex> без коллизий. Очевидно, что <tex>h_{a}(x)</tex> может быть посчитана для любого <tex>x</tex> за константное время. Если мы упакуем несколько чисел в один контейнер так, что они разделены несколькими битами нулей, мы спокойно сможем применить <tex>h_{a}</tex> ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только (mod <tex>2^b</tex>) и (div <tex>2^{b - s}</tex>).

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

Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, ..., <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество чисeл. Мы хотим разделить <tex>S</tex> в <tex>p + 1</tex> наборов таких, что: <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < {<tex>a_{2}</tex>} < ... < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Т.к. мы используем signature sorting, до того как делать вышеописанное разделение, мы поделим биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов и возьмем некоторые из них. Мы так же поделим биты для каждого числа из <tex>S</tex> и оставим только один в каждом числе. По существу для каждого <tex>a_{i}</tex> мы возьмем все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегменты, которые мы берем для числа в <tex>S</tex>, {{---}} сегмент, который выделяется из <tex>a_{i}</tex>. Таким образом мы преобразуем начальную задачу о разделении <tex>n</tex> чисел в <tex>logm\log m</tex> бит в несколько задач на разделение с числами в <tex>\log(m/h)</tex> бит.

<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(nloglognn \log\log n/logk\log k)</tex> и место <tex>O(n)</tex> с не консервативным преимуществом <tex>kloglognk \log\log n</tex>

Выбор <tex>s</tex>-ого наибольшего числа среди <tex>n</tex> чисел упакованных в <tex>n/g</tex> контейнеров может быть сделана за <tex>O(nloggn \log g/g)</tex> время и с использованием <tex>O(n/g)</tex> места. Конкретно медиана может быть так найдена.

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

Так как используется только <tex>(logn\log n)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, мы можем использовать bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает <tex>O(n/g)</tex> времени и места. Потому, что мы используем <tex>(logn\log n)/2</tex> бит на контейнер нам понадобится <tex>\sqrt {n}</tex> шаблонов для всех контейнеров. Затем поместим <tex>g < (logn\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(gloggg \log g)</tex>, с использованием <tex>O(g)</tex> места. Для всех групп это занимает время <tex>O((n/g)logg\log g)</tex>, с использованием <tex>O(n/g)</tex> места.

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

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

Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>(logn\log n)/2</tex> бит. Сортировка сгруппирует контейнеры для чисел как в четвертой лемме. Мы можем переместить каждую группу контейнеров для чисел.

предположим, что каждый контейнер содержит <tex>logmloglogn \log m \log\log n > logn\log n</tex> бит, что <tex>g</tex> чисел, в каждом из которых <tex>(logm\log m)/g</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>(logn\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>logmloglogn\log m \log\log n</tex> бит всего <tex>logm\log m</tex> бит используется для хранения упакованных чисел. Так же как в леммах четыре и пять мы сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел мы помещаем <tex>gloglogng \log\log n</tex> вместо <tex>g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе содержащей <tex>gloglogng \log\log n</tex> контейнеров мы сначала упаковываем <tex>gloglogng \log\log n</tex> контейнеров в <tex>g</tex> контейнеров упаковывая <tex>loglogn\log\log n</tex> контейнеров в один. Далее мы делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего <tex>O(gloglogng \log\log n)</tex> времени для каждой группы и <tex>O(n/g)</tex> времени для всех чисел. После завершения транспозиции, мы далее распаковываем <tex>g</tex> контейнеров в <tex>gloglogng \log\log n</tex> контейнеров.

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

Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества {0, 1, ..., <tex>m</tex> - 1} в <tex>\sqrt{n}</tex> наборов как во второй лемме. Мы предполагаем, что в каждом контейнере <tex>kloglognlogmk \log\log n \log m</tex> бит и хранит число в <tex>logm\log m</tex> бит. Поэтому неконсервативное преимущество <tex>kloglognk \log \log n</tex>. Мы так же предполагаем, что <tex>logm \log m >= lognloglogn\log n \log\log n</tex>. Иначе мы можем использовать radix sort для сортировки за время <tex>O(nloglognn \log\log n)</tex> и линейную память. Мы делим <tex>logm\log m</tex> бит, используемых для представления каждого числа, в <tex>logn\log n</tex> блоков. Таким образом каждый блок содержит как минимум <tex>loglogn\log\log n</tex> бит. <tex>i</tex>-ый блок содержит с <tex>ilogmi \log m/logn\log n</tex>-ого по <tex>((i + 1)logm\log m/logn \log n - 1)</tex>-ый биты. Биты считаются с наименьшего бита начиная с нуля. Теперь у нас имеется <tex>2logn2 \log n</tex>-уровневый алгоритм, который работает следующим образом:

На каждой стадии мы работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.) потому, что каждое м.ч. теперь содержит только <tex>logm\log m/logn\log n</tex> бит. Каждое число представлено и соотносится с м.ч., над которым мы работаем в данный момент. Положим, что нулевая стадия работает с самыми большим блоком (блок номер <tex>logn \log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>n/logn\log n</tex> контейнеров с <tex>logn\log n</tex> м.ч. упакованных в один контейнер. Мы пренебрегаем временем, потраченным на на эту упаковку, считая что она бесплатна. По третьей лемме мы можем найти медиану этих <tex>n</tex> м.ч. за время и память <tex>O(n/logn\log n)</tex>. Пусть <tex>a</tex> это найденная медиана. Тогда <tex>n</tex> м.ч. могут быть разделены на не более чем три группы: <tex>S_{1}</tex>, <tex>S_{2}</tex> и <tex>S_{3}</tex>. <tex>S_{1}</tex> содержит м.ч. которые меньше <tex>a</tex>, <tex>S_{2}</tex> содержит м.ч. равные <tex>a</tex>, <tex>S_{3}</tex> содержит м.ч. большие <tex>a</tex>. Так же мощность <tex>S_{1}</tex> и <tex>S_{3} </tex><= <tex>n/2</tex>. Мощность <tex>S_{2}</tex> может быть любой. Пусть <tex>S'_{2}</tex> это набор чисел, у которых наибольший блок находится в <tex>S_{2}</tex>. Тогда мы можем убрать убрать <tex>logm\log m/logn\log n</tex> бит (наибольший блок) из каждого числа из <tex>S'_{2}</tex> из дальнейшего рассмотрения. Таким образом после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex>logn\log n</tex> блоков, для каждого числа потребуется не более <tex>logn\log n</tex> стадий чтобы поместить его в набор половинного размера. За <tex>2logn2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии мы работаем с <tex>n/logn\log n</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, мы затратим <tex>O(n)</tex> времени из-за <tex>2logn2 \log n</tex> стадий.

Сложная часть алгоритма заключается в том, как поместить маленькие числа в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Мы можем использовать <tex>loge\log e</tex> битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать лемму шесть. Полный размер маркера для каждого контейнера должен быть <tex>logn\log n/2</tex>, и маркер использует <tex>loge\log e</tex> бит, количество маркеров <tex>g</tex> в каждом контейнере должно быть не более <tex>logn\log n/(2loge2\log e)</tex>. В дальнейшем т.к. <tex>g = logn\log n/(2loge2 \log e)</tex> м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex>kloglognlognk \log\log n \log n</tex> блоков, каждое м.ч. может содержать <tex>O(klognk \log n/g) = O(klogek \log e)</tex> блоков. Заметим, что мы используем неконсервативное преимущество в <tex>loglogn\log\log n</tex> для использования леммы шесть. Поэтому мы предполагаем что <tex>logn\log n/(2loge2 \log e)</tex> м.ч. в каждом из которых <tex>klogek \log e</tex> блоков битов числа упакованный в один контейнер. Для каждого м.ч. мы используем маркер из <tex>loge\log e</tex> бит, который показывает к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры как и м.ч. Так как каждый контейнер для маркеров содержит <tex>logn\log n/(2loge2 \log e)</tex> маркеров, то для каждого контейнера требуется <tex>(logn\log n)/2</tex> бит. Таким образом лемма шесть может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O((nlogen \log e)/logn\log n)</tex> контейнеров то время необходимое для помещения м.ч. в их наборы потребуется <tex>O((nlogen \log e)/logn\log n)</tex> времени.

Рассмотрим число <tex>a</tex>, которое является <tex>i</tex>-ым в наборе <tex>S</tex>. Рассмотрим блок <tex>a</tex> (назовем его <tex>a'</tex>), который является <tex>i</tex>-ым м.ч. в <tex>S</tex>. Когда мы используем вышеописанный метод перемещения нескольких следующих блоков <tex>a</tex> (назовем это <tex>a''</tex>) в <tex>S</tex>, <tex>a''</tex> просто перемещен на позицию в наборе <tex>S</tex>, но не обязательно на позицию <tex>i</tex> (где расположен <tex>a'</tex>). Если значение блока <tex>a'</tex> одинаково для всех чисел в <tex>S</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex>S</tex> помещен <tex>a''</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому мы поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда мы помещаем больше бит в набор мы помещаем последующие блоки вместе с текущим блоком в набор. Так вот, в вышеописанном процессе помещения мы предполагаем, что самый значимый блок среди <tex>klogek \log e</tex> блоков это текущий блок. Таким образом после того как мы поместили эти <tex>klogek \log e</tex> блоков в набор мы удаляем изначальный текущий блок, потому что мы знаем, что эти <tex>klogek \log e</tex> блоков перемещены в правильный набор и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex>klogek \log e</tex> блоках.

Algorithm Sort(<tex>kloglognk \log\log n</tex>, <tex>level</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, ..., <tex>a_{t}</tex>)

<tex>kloglognk \log\log n</tex> это неконсервативное преимущество, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, <tex>level</tex> это уровень рекурсии.

2.2) Вызвать Sort(<tex>kloglognk \log\log n</tex>, <tex>level - 1</tex>, <tex>a^{(u)}_{0}</tex>, <tex>a^{(u)}_{1}</tex>, ..., <tex>a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к которому набору это число относится, уже отправлен назад к месту где число находится во входных данных. Число имеющее наибольшее число бит в <tex>a_{i}</tex>, показывающее на ткущий блок в нем, так же отправлено назад к <tex>a_{i}</tex>.

Call Sort(<tex>kloglognk \log\log n</tex>, <tex>\log_{k}((logn\log n)/4)</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, ..., <tex>a_{n - 1}</tex>);

Для каждого набора <tex>S = </tex>{<tex>a_{i_{0}}, a_{i_{1}}, ..., a_{i_{t}}</tex>}, если <tex>t > sqrt{n}</tex>, вызвать Sort(<tex>kloglognk \log\log n</tex>, <tex>\log_{k}((logn\log n)/4)</tex>, <tex>a_{i_{0}}, a_{i_{1}}, ..., a_{i_{t}}</tex>)

Время работы алгоритма <tex>O(nloglognn \log\log n/logk\log k)</tex>, что доказывает лемму 2.

==Собственно сортировка с использованием O(nloglognn \log\log n) времени и памяти==Для сортировки <tex>n</tex> целых чисел в диапазоне от {<tex>0, 1, ..., m - 1</tex>} мы предполагаем, что используем контейнер длины <tex>O(\log(m + n))</tex> в нашем консервативном алгоритме. Мы всегда считаем что все числа упакованы в контейнеры одинаковой длины.

Нетрудно заметить, что ребалансирока занимает <tex>O(nloglognn \log\log n)</tex> времени с <tex>O(n)</tex> временем на уровень. Аналогично стандартному Э.П.дереву Андерссона.

Для этого воспользуемся signature sorting. Адаптируем этот алгоритм для нас. Предположим у нас есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, ..., a_{p}</tex>, и мы хотим использовать числа в <tex>T</tex> для разделения <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, ..., b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, ..., S_{p}</tex> что <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < ... < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами. Пусть <tex>h = logn\log n/(clogpc \log p)</tex> для константы <tex>c > 1</tex>. <tex>h/loglognlogp\log\log n \log p</tex> битные числа могут быть хранены в одном контейнере, так что одно слово хранит <tex>(logn\log n)/(cloglognc \log\log n)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины <tex>h/loglogn\log\log n</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки мы хэштруем числа в этих контейнерах (<tex>a_{i}</tex>-ом и <tex>b_{i}</tex>-ом) чтобы получить <tex>h/loglogn\log\log n</tex> хэшированных значений в одном контейнере. Чтобы получить значения сразу, при вычислении хэш значений сегменты не влияют друг на друга, мы можем даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хэш значения считаются за константное время. Затем, посчитав значения мы объединяем два контейнера в один. Пусть <tex>a'_{i}</tex> хэш контейнер для <tex>a_{i}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хэш значения имеют <tex>(2logn2 \log n)/(cloglognc \log\log n)</tex> бит. Хотя эти значения разделены на сегменты по <tex>h/loglogn\log\log n</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые мы забиваем нулями. Сначала упаковываем все сегменты в <tex>(2logn2 \log n)/(cloglognc \log\log n)</tex> бит. Потом рассмотрим каждый хэш контейнер как число и отсортируем эти хэш слова за линейное время (сортировка рассмотрена чуть позже). После этой сортировки биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>loglogn\log\log n/h</tex>. Таким образом мы получили дополнительное мультипликативное преимущество в <tex>h/loglogn\log\log n</tex> (additional multiplicative advantage).

После того, как мы повторили вышеописанный процесс <tex>g</tex> раз мы получили неконсервативное преимущество в <tex>(h/loglogn\log\log n)^g</tex> раз, в то время как мы потратили только <tex>O(gqt)</tex> времени, так как каждое многократное деление делятся за линейное время <tex>O(qt)</tex>.

Хэш функция, которую мы используем, находится следующим образом. Мы будем хэшировать сегменты, которые <tex>loglogn\log\log n/h</tex>-ые, <tex>(loglogn\log\log n/h)^2</tex>-ые, ... от всего числа. Для сегментов вида <tex>(loglogn\log\log n/h)^t</tex>, получаем нарезанием всех <tex>p</tex> чисел на <tex>(loglogn\log\log n/h)^t</tex> сегментов. Рассматривая каждый сегмент как число мы получаем <tex>p(loglogn\log\log n/h)^t</tex> чисел. Затем получаем одну хэш функцию для этих чисел. Так как <tex>t < logn\log n</tex> то мы получим не более <tex>logn\log n</tex> хэш функций.

Рассмотрим сортировку за линейное время о которой было упомянуто ранее. Предполагаем, что мы упаковали хэшированные значения для каждого контейнера в <tex>(2logn2 \log n)/(cloglognc \log\log n)</tex> бит. У нас есть <tex>t</tex> наборов в каждом из которых <tex>q + p</tex> хэшированных контейнеров по <tex>(2logn2 \log n)/(cloglognc \log\log n)</tex> бит в каждом. Эти числа должны быть отсортированы в каждом наборе. Мы комбинируем все хэш контейнеры в один pool и сортируем следующим образом.

Входные данные: <tex>r > = n^{2/5}</tex> чисел <tex>d_{i}</tex>, <tex>d_{i}</tex>.value значение числа <tex>d_{i}</tex> в котором <tex>(2logn2 \log n)/(cloglognc \log\log n)</tex> бит, <tex>d_{i}.set</tex> набор, в котором находится <tex>d_{i}</tex>, следует отметить что всего <tex>t</tex> наборов.

Как уже говорилось ранее после <tex>g</tex> сокращений бит мы получили неконсервативное преимущество в <tex>(h/loglogn\log\log n)^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на лемму два для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборы. Заметим, что по природе битового сокращения, начальная задача разделения для каждого набора перешла в <tex>w</tex> подзадачи разделения на <tex>w</tex> поднаборы для какого-то числа <tex>w</tex>.

Теперь для каждого набора мы собираем все его поднаборы в подзадачах в один набор. Затем используя лемму два делаем разделение. Так как мы имеем неконсервативное преимущество в <tex>(h/loglogn\log\log n)^g</tex> и мы работаем на уровнях не ниже чем <tex>2logloglogn2 \log\log\log n</tex>, то алгоритм занимает <tex>O(qtloglognqt \log\log n/(g(logh \log h - logloglogn\log\log\log n) -logloglogn\log\log\log n)) = O(loglogn\log\log n)</tex> времени.

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

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

Deterministic Sorting in O(nloglognn \log\log n) Time and Linear Space. Yijie Han.