Изменения

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

Данная статья писалась на основе брошюры Хана(англ. ''Yijie Han''), посвященной этой сортировке. Изложение материала в данной статье идет примерно в том же порядке, в каком она предоставлена в работе Хана.

== Алгоритм Описание ==Алгоритм построен на основе '''экспоненциального поискового дерева Андерсона''' (далее {{---}} Эангл.П.дерево) Андерсона (''Andersson's exponential search tree''). Сортировка происходит за счет вставки целых чисел в Э.П.экспоненциальное поисковое дерево (''далее {{---}} ЭП-дерево'').

== Andersson's exponential search tree Экспоненциальное поисковое дерево Андерсона ==Э.П.дерево с <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\log n)</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(n \log\log n)</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

|id=def1. |definition=Контейнер '''ЭП-дерево''' {{---}} объект определенного типа, содержащий обрабатываемый элемент. Например __int32, __int64это дерево поиска, в котором все ключи хранятся в листьях этого дерева и т.дколичество детей у каждого узла уменьшается экспоненциально от глубины узла.

 [[Файл:Exp-tree.png|400px|thumb|right|Общая структура ЭП-дерева]] Структура ЭП-дерева: 1) Корень имеет <tex dpi="130">\Theta (n^e)</tex> сыновей <tex dpi="130">( 0 < e < 1 )</tex>. Все сыновья являются ЭП-деревьями. 2) Каждое поддерево корня имеет <tex dpi="130">\Theta(n^{1-e})</tex> сыновей. В этом дереве <tex dpi="130">O(n \log\log n)</tex> уровней. При нарушении баланса дерева необходимо балансирование, которое требует <tex dpi="130">O(n \log\log n)</tex> времени при <tex dpi="130">n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон. ==Определения== {{Определение|iddefinition =def2 '''Контейнер''' {{---}} объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора. }}{{ Определение |definition= Алгоритм , сортирующий <texdpi="130">n</tex> целых чисел из множества <texdpi="130">\{0, 1, \ldots, m - 1\}</tex> , называется '''консервативным''', если длина контейнера (число бит в контейнере), является равна <texdpi="130">O(\log(m + n))</tex>. Если длина больше, то алгоритм '''неконсервативный'''. }}{{ Определение | definition = Если сортируются целые числа из множества <tex dpi="130">\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex dpi="130">k \log (m + n)</tex> с <tex dpi="130">k \geqslant 1</tex>, тогда сортировка происходит с '''неконсервативным преимуществом''' <tex dpi="130">k</tex>.

{{Определение|id=def3. |definition=Если мы сортируем целые числа из Для множества {0, 1, ..., <texdpi="130">mS</tex> - 1определим <tex dpi="130">\min(S) = \min\limits_{a \in S} с длиной контейнера a</tex>klog <tex dpi="130">\max(m + nS)= \max\limits_{a \in S} a</tex> с  Набор <texdpi="130">kS1 < S2</tex> >= 1, тогда мы сортируем с неконсервативным преимуществом если <texdpi="130">k\max(S1) \leqslant \min(S2)</tex>.

 {{Определение|id=def4. |definition=Для множества Предположим, есть набор <texdpi="130">ST</tex> определимmin(из <texdpi="130">Sp</tex>) = min(чисел, которые уже отсортированы как <texdpi="130">aa_{1}, a_{2}, \ldots, a_{p}</tex>:и набор <texdpi="130">aS</tex> принадлежит из <texdpi="130">Sq</tex>)max(чисел <texdpi="130">Sb_{1}, b_{2}, \ldots, b_{q}</tex>) = max(. Тогда '''разделением''' <texdpi="130">aq</tex>:чисел <texdpi="130">ap</tex> принадлежит числами называется <texdpi="130">Sp + 1</tex>)Набор набор <texdpi="130">S1S_{0}, S_{1}, \ldots, S_{p}</tex> < , где <texdpi="130">S2S_{0} </tex> если max(a_{1} <tex>S1S_{1} </tex>) \ldots <= min(a_{p} <tex>S2S_{p}</tex>).

==Уменьшение числа бит в числахЛеммы==Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и Raman.

Алгоритм: Пусть целое число {{Лемма|id = lemma1|about = № 1|statement = Даны целые числа <texdpi="130">b >= \geqslant s \geqslant 0</tex> , и пусть <tex dpi="130">T</tex>U является подмножеством множества <tex dpi= "130">\{0, \ldots, 2^b - 1\}</tex>. Класс <tex>H_{b,s}</tex> хэш функций из содержащим <texdpi="130">Un</tex> в элементов, и <texdpi="130">t \{0, \ldots, geqslant 2^{-s - + 1\}С^k_{n}</tex> определен как . Функция <texdpi="130">H_{b,s} = \{h_{a} \mid 0 < a /tex>, принадлежащая < 2^tex dpi="130">H_{b, a \equiv 1 (\mod 2)\s}</tex> и для всех , может быть выбрана за время <texdpi="130">xO(bn^2)</tex> из так, что количество коллизий <texdpi="130">U: coll(h_{a}(x, T) = (ax \mod 2^b) div 2^{b - s}leqslant t</tex>.}}

|id=lemma1. lemma2|about = № 2|statement=Даны целые Выбор <tex dpi="130">s</tex>-ого наибольшего числа среди <texdpi="130">bn</tex> чисел, упакованных в <tex dpi="150">\frac{n}{g}</tex>= контейнеров, может быть сделан за время <texdpi="150">sO(\frac{n \log g}{g})</tex> >= 0 и с использованием <texdpi="150">TO(\frac{n}{g})</tex> является подмножеством {0памяти. В том числе, так может быть найдена медиана...,  |proof = Так как возможно делать попарное сравнение <texdpi="130">2^bg</tex> - 1}, содержащим чисел в одном контейнере с <texdpi="130">ng</tex> элементовчислами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, и <texdpi="130">t\ldots</tex> , <tex dpi="130">= g</tex>2^{-s + 1}ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор <tex dpi="130">S</tex>Сиз медиан теперь содержится в <texdpi="150">^k_\frac{n}{5g}</tex>контейнерах. Функция Рекурсивно находим медиану <texdpi="130">h_{a}m</tex> в <tex dpi="130">S</tex>. Используя <tex dpi="130">m</tex> принадлежащая , уберем хотя бы <texdpi="150">H_\frac{b,sn}{4}</tex> может быть выбрана за время чисел среди <texdpi="130">O(bn^2)n</tex> так, что количество коллизий . Затем упакуем оставшиеся из <texdpi="150">coll(h_\frac{n}{ag}, T) </tex> контейнеров в <tex dpi= t"150">\frac{3n}{4g}</tex>контейнеров и затем продолжим рекурсию.

Взяв {{Лемма|id = lemma3|about = № 3|statement = Если <texdpi="130">s = 2logng</tex> мы получим хэш функцию целых чисел, в сумме использующих <texdpi="150">h_\frac{a\log n}{2}</tex> которая захэширует бит, упакованы в один контейнер, тогда <texdpi="130">n</tex> чисел из <tex>U</tex> в таблицу размера <texdpi="150">O(\frac{n^2)</tex> без коллизий. Очевидно, что <tex>h_}{ag}(x)</tex> может контейнерах могут быть посчитана для любого <tex>x</tex> отсортированы за константное время. Если мы упакуем несколько чисел в один контейнер так, что они разделены несколькими битами нулей, мы спокойно сможем применить <texdpi="150">h_O(\frac{an \log g}{g})</tex> ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только (mod <tex>2^bс использованием </texdpi="150">) и O(div <tex>2^\frac{n}{b - sg})</tex>)памяти.

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

Для контейнеров вне групп (которых <tex dpi="130">\sqrt{n}(g - 1)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется не более <tex dpi=Signature sorting"150">O(\frac{n}{g})</tex> времени и памяти. После всего этого используем карманную сортировку вновь для сортировки <tex dpi==В данной сортировке используется следующий алгоритм:"130">n</tex> контейнеров. Таким образом, все числа отсортированы.

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

Пример{{Лемма|id = lemma4|about = № 4|statement = Примем, что каждый контейнер содержит <tex dpi="130"> \log m > \log n</tex> бит, и <tex dpi="130">g</tex> чисел, в каждом из которых <tex dpi="150">\frac{\log m}{g}</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex dpi="150">\frac{\log n}{2g}</tex> бит, и <tex dpi="130">g</tex> маркеров упакованы в один контейнер таким же образом<tex dpi="130">^*</tex>, что и числа, тогда <tex dpi="130">n</tex> чисел в <tex dpi="150">\frac{n}{g}</tex> контейнерах могут быть отсортированы по их маркерам за время <tex dpi="150">O(\frac{n \log\log n}{g})</tex> с использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти.(*):если число <tex dpi="130">a</tex> упаковано как <tex dpi="130">s</tex>-ое число в <tex dpi="130">t</tex>-ом контейнере для чисел, тогда маркер для <tex dpi="130">a</tex> упакован как <tex dpi="130">s</tex>-ый маркер в <tex dpi="130">t</tex>-ом контейнере для маркеров.

Мы разделим числа на 2 сегмента. Для |proof = Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <texdpi="150">a_\frac{1\log n}</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2}</tex> верхний 1, нижний 1; <tex>a_{3}</tex> верхний 1, нижний 3; <tex>a_{4}</tex> верхний 2, нижний 2бит. Для элементов из S получим: Сортировка сгруппирует контейнеры для 1: нижний 1 тчисел как в [[#lemma3|лемме №3]].кПеремещаем каждую группу контейнеров для чисел. он выделяется из нижнего сегмента <tex>a_{1}}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.

|id=lemma2. lemma5|about = № 5|statement=Предположим, что каждый контейнер содержит <texdpi="130">\log m \log\log n >\log n</tex> целых бит, что <tex dpi="130">g</tex> чисел можно отсортировать , в каждом из которых <texdpi="150">\sqrtfrac{n\log m}{g}</tex> наборов бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <texdpi="150">S_\frac{\log n}{12g}</tex>бит, и что <tex dpi="130">g</tex> маркеров упакованы в один контейнер тем же образом что и числа. Тогда <texdpi="130">S_n</tex> чисел в <tex dpi="150">\frac{2n}{g}</tex>, ..., контейнерах могут быть отсортированы по своим маркерам за время <texdpi="150">S_O(\frac{n}{g})</tex> с использованием <tex dpi="150">O(\sqrtfrac{n}{g})</tex> таким образомпамяти. |proof = Заметим, что несмотря на то, что в каждом наборе длина контейнера <texdpi="130">\sqrt{log m \log\log n}</tex> бит, всего <tex dpi="130">\log m</tex> бит используется для хранения упакованных чисел . Так же как в [[#lemma3|лемме №3]] и [[#lemma4|лемме №4]] сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем <texdpi="130">S_{i}g \log\log n</tex> вместо < tex dpi="130">g</tex>S_{j}контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей <tex dpi="130">g \log\log n</tex> при контейнеров, упаковываем <texdpi="130">ig \log\log n</tex> контейнеров в < tex dpi="130">g</tex>j, упаковывая <tex dpi="130">\log\log n</tex>, за время контейнеров в один. Далее делаем транспозицию над <tex dpi="130">g</tex> контейнерами. Таким образом перемещение занимает всего <texdpi="130">O(nloglogn/logkg \log\log n)</tex> времени для каждой группы и место <texdpi="150">O(\frac{n}{g})</tex> с не консервативным преимуществом времени для всех чисел. После завершения транспозиции, распаковываем <tex dpi="130">g</tex> контейнеров в <texdpi="130">kloglogng \log\log n</tex>контейнеров.  Заметим, что если длина контейнера <tex dpi="130">\log m \log\log n</tex> и только <tex dpi="130">\log m</tex> бит используется для упаковки <tex dpi="130">g \leqslant \log n</tex> чисел в один контейнер, тогда выбор в [[#lemma2|proofлемме №2]] может быть сделан за время и память <tex dpi=Доказательство данной леммы будет приведено далее "150">O(\frac{n}{g})</tex>, потому что упаковка в тексте статьидоказательстве [[#lemma2|лемме №2]] теперь может быть сделана за время <tex dpi="150">O(\frac{n}{g})</tex>.

Номер три. 

|id=lemma3lemma6|about = № 6|statement = <tex dpi="130">n</tex> целых чисел можно отсортировать в <tex dpi="130">\sqrt{n}</tex> наборов <tex dpi="130">S_{1}</tex>, <tex dpi="130">S_{2}</tex>, <tex dpi="130">\ldots</tex>, <tex dpi="130">S_{\sqrt{n}}</tex> таким образом, что в каждом наборе <tex dpi="130">\sqrt{n}</tex> чисел и <tex dpi="130">S_{i} < S_{j}</tex> при <tex dpi="130">i < j</tex>, за время <tex dpi="150">O(\frac{n \log\log n} {\log k})</tex> и место <tex dpi="130">O(n)</tex> с неконсервативным преимуществом <tex dpi="130">k \log\log n</tex>.   |statementproof =Выбор Алгоритм сортировки <tex dpi="130">n</tex> целых чисел в <texdpi="130">s\sqrt{n}</tex>наборов, представленный ниже, является доказательством данной леммы.  Постановка задачи и решение некоторых проблем:  Рассмотрим проблему сортировки <tex dpi="130">n</tex> целых чисел из множества <tex dpi="130">\{0, 1, \ldots, m -ого наибольшего числа среди 1\}</tex> в <tex dpi="130">\sqrt{n}</tex> наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит <texdpi="130">k \log\log n\log m</tex> чисел упакованных бит и хранит число в <texdpi="130">\log m</tex> бит. Поэтому неконсервативное преимущество {{---}} <tex dpi="130">k \log \log n</gtex>. Также предполагаем, что <tex dpi="130">\log m \geqslant \log n \log\log n</tex> контейнеров может быть сделана . Иначе можно использовать radix sort для сортировки за время <texdpi="130">O(nloggn \log\log n)</tex> и линейную память. Делим <tex dpi="130">\log m</tex> бит, используемых для представления каждого числа, в <tex dpi="130">\log n</tex> блоков. Таким образом, каждый блок содержит как минимум <tex dpi="130">\log\log n</tex> бит. <tex dpi="130">i</tex>-ый блок содержит с <tex dpi="150">\frac{i \log m} {\log n}</tex>-ого по <tex dpi="150">(\frac{(i + 1) \log m} {\log n - 1})</tex>-ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <tex dpi="130">2 \log n</tex>-уровневый алгоритм, который работает следующим образом:  На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.), потому что каждое м.ч. теперь содержит только <tex dpi="150">\frac{\log m}{\log n}</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер <tex dpi="130">\log n - 1</gtex>). Предполагаем, что биты этих м.ч. упакованы в <tex dpi="150">\frac{n}{\log n}</tex> контейнеров с <tex dpi="130">\log n</tex> м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на эту упаковку, считаем, что она бесплатна. По [[#lemma2|лемме №2]] находим медиану этих <tex dpi="130">n</tex> м.ч. за время и с использованием память <texdpi="150">O(\frac{n/g}{\log n})</tex> места. Конкретно Пусть <tex dpi="130">a</tex> {{---}} это найденная медиана . Тогда <tex dpi="130">n</tex> м.ч. могут быть разделены на не более чем три группы: <tex dpi="130">S_{1}</tex>, <tex dpi="130">S_{2}</tex> и <tex dpi="130">S_{3}</tex>. <tex dpi="130">S_{1}</tex> содержит м.ч., которые меньше <tex dpi="130">a</tex>, <tex dpi="130">S_{2}</tex> содержит м.ч., равные <tex dpi="130">a</tex>, <tex dpi="130">S_{3}</tex> содержит м.ч., большие <tex dpi="130">a</tex>. Также мощность <tex dpi="130">S_{1}</tex> и <tex dpi="130">S_{3} </tex> не превосходит <tex dpi="130">n/2</tex>. Мощность <tex dpi="130">S_{2}</tex> может быть так найденалюбой. Пусть <tex dpi="130">S'_{2}</tex> {{---}} это набор чисел, у которых наибольший блок находится в <tex dpi="130">S_{2}</tex>.|proofТогда убираем из дальнейшего рассмотрения <tex dpi="150">\frac{\log m}{\log n}</tex> бит (наибольший блок) из каждого числа, принадлежащего <tex dpi="130">S'_{2}</tex>. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как мы можем делать попарное сравнение в каждом числе только <texdpi="130">g\log n</tex> блоков, для каждого числа потребуется не более <tex dpi="130">\log n</tex> чисел стадий, чтобы поместить его в одном контейнере набор половинного размера. За <tex dpi="130">2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <texdpi="150">g\frac{n}{\log n}</tex> числами контейнерами, то игнорируя время, необходимое на упаковку м.ч. в другом контейнеры и извлекать большие числа помещение м.ч. в нужный набор, затрачивается <tex dpi="130">O(n)</tex> времени из одного -за <tex dpi="130">2 \log n</tex> стадий.  Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex dpi="130">n</tex> чисел уже поделены в <tex dpi="130">e</tex> наборов. Используем <tex dpi="130">\log e</tex> битов чтобы сделать марки для каждого набора. Теперь используем [[#lemma5|лемме №5]]. Полный размер маркера для каждого контейнера должен быть <tex dpi="150">\frac{\log n}{2}</tex>, и меньшие из другого за константное времямаркер использует <tex dpi="130">\log e</tex> бит, мы можем упаковать медианы из первогозначит количество маркеров <tex dpi="130">g</tex> в каждом контейнере должно быть не более <tex dpi="150">\frac{\log n}{2\log e}</tex>. В дальнейшем, второготак как <tex dpi="150">g = \frac{\log n}{2 \log e}</tex>, м.ч.должны влезать в контейнер.Каждый контейнер содержит <tex dpi="130">k \log\log n \log n</tex> блоков, каждое м.ч. может содержать <texdpi="150">O(\frac{k \log n}{g}) = O(k \log e)</tex>-ого чисел блоков. Заметим, что используется неконсервативное преимущество в <tex dpi="130">\log\log n</tex> для [[#lemma5|лемме №5]] Поэтому предполагается, что <tex dpi="150">\frac{\log n}{2 \log e}</tex> м.ч., в каждом из 5 контейнеров которых <tex dpi="130">k \log e</tex> блоков битов числа, упакованны в один контейнер за константное . Для каждого м.ч. используется маркер из <tex dpi="130">\log e</tex> бит, который показывает, к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры, как и м.ч. Так как каждый контейнер для маркеров содержит <tex dpi="150">\frac{\log n}{2 \log e}</tex> маркеров, то для каждого контейнера требуется <tex dpi="150">\frac{\log n}{2}</tex> бит. Таким образом, [[#lemma5|лемма №5]] может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex dpi="150">O(\frac{n \log e}{ \log n})</tex> контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно <tex dpi="150">O(\frac{n \log e}{ \log n})</tex>. Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из [[#lemma5|леммы №5]].  При таком помещении сразу возникает следующая проблема. Рассмотрим число <tex dpi="130">a</tex>, которое является <tex dpi="130">i</tex>-ым в наборе <tex dpi="130">S</tex>. Рассмотрим блок <tex dpi="130">a</tex> (назовем его <tex dpi="130">a'</tex>), который является <tex dpi="130">i</tex>-ым м.ч. в <tex dpi="130">S</tex>. Когда используется вышеописанный метод перемещения нескольких следующих блоков <tex dpi="130">a</tex> (назовем это <tex dpi="130">a''</tex>) в <tex dpi="130">S</tex>, <tex dpi="130">a''</tex> просто перемещен на позицию в наборе <tex dpi="130">S</tex>, но не обязательно на позицию <tex dpi="130">i</tex> (где расположен <tex dpi="130">a'</tex>). Если значение блока <tex dpi="130">a'</tex> одинаково для всех чисел в <tex dpi="130">S</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex dpi="130">S</tex> помещен <tex dpi="130">a''</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, последующие блоки помещаются в набор вместе с текущим блоком. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <tex dpi="130">k \log e</tex> блоков {{---}} это текущий блок. Таким образом , после того, как эти <tex dpi="130">k \log e</tex> блоков помещены в набор , изначальный текущий блок удаляется, потому что известно, что эти <tex dpi="130">k \log e</tex>Sблоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex dpi="130">k \log e</tex> блоках.  Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы [[#lemma3|3]], [[#lemma4|4]], [[#lemma5|5]] расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из медиан теперь содержится <tex dpi="130">n</tex> элементов в наборы размера <texdpi="130">\sqrt{n}</tex>, то проблем быть не должно.  ===Алгоритм сортировки=== Algorithm <tex>Sort(5gadvantage</tex>, <tex>level</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots</tex>, <tex>a_{t}</tex>) <tex>advantage</tex> {{---}} это неконсервативное преимущество равное <tex>k\log\log n</tex>, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, <tex>level</tex> контейнерахэто уровень рекурсии. Рекурсивно находим  # Если <tex>level</tex> равен <tex>1</tex> тогда изучаем размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе делим этот набор в <tex>\leqslant</tex> 3 набора, используя [[#lemma2|лемму №2]], чтобы найти медиану , а затем используем [[#lemma5|лемму №5]] для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.# От <tex dpi="130">u = 1</tex> до <tex dpi="130">k</tex>## Упаковываем <tex dpi="130">a^{(u)}_{i}</tex>-ый в часть из <tex dpi="130">1/k</tex>-ых номеров контейнеров. Где <texdpi="130">ma^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex dpi="150">\frac{1}{k}</tex>-ых битов <tex dpi="130">a_{i}</tex>. При этом у <tex dpi="130">a^{(u)}_{i}</tex> текущий блок это самый крупный блок.## Вызываем <tex>Sort(advantage</tex>, <tex>level - 1</tex>, <tex dpi="130">a^{(u)}_{0}</tex>, <tex dpi="130">a^{(u)}_{1}</tex>, <tex>\ldots</tex>, <tex dpi="130">a^{(u)}_{t}</tex> ). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к какому набору это число относится, уже направлен назад к месту, где число находится во входных данных. Число, имеющее наибольшее число бит в <tex dpi="130">a_{i}</tex>S, показывающее на текущий блок в нем, так же направлено назад к <tex dpi="130">a_{i}</tex>.## Отправляем <tex dpi="130">a_{i}</tex>-ые к их наборам, используя [[#lemma5|лемму №5]]. Используя  Algorithm IterateSortCall <tex>mSort(advantage</tex> уберем хотя бы , <texdpi="130">\log_{k}((\log n)/4)</tex> чисел среди , <tex dpi="130">a_{0}</tex>, <tex dpi="130">a_{1}</tex>, <tex dpi="130">\ldots</tex>, <tex dpi="130">a_{n - 1}</tex>); от 1 до 5# Помещаем <tex dpi="130">a_{i}</tex> в соответствующий набор с помощью блочной сортировки (англ. ''bucket sort''), потому что наборов около <texdpi="130">\sqrt{n}</tex>. Затем упакуем оставшиеся из # Для каждого набора <tex dpi="130">S = </tex>{<tex dpi="130">a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>}, если <texdpi="130">t > \sqrt{n}</tex>, вызываем <tex>Sort(advantage</gtex>, <tex dpi="130">\log_{k}(\frac{\log n}{4})</tex> контейнеров в , <texdpi="130">3na_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</4gtex>). Время работы алгоритма <tex dpi="150">O(\frac{n \log\log n}{\log k})</tex> контейнеров и затем продолжим рекурсию, что доказывает лемму.

Лемма пять==Уменьшение числа бит в числах==Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза.Это быстрый способ, требующий <tex dpi="130">O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex dpi="130">O(n)</tex>. Для того чтобы еще ускорить алгоритм, необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш-функция для хеширования <tex dpi="130">n</tex> чисел в таблицу размера <tex dpi="130">O(n^2)</tex> за константное время без коллизий. Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger и Raman.  Алгоритм: Пусть целое число <tex dpi="130">b \geqslant 0</tex> и пусть <tex dpi="130">U = \{0, \ldots, 2^b - 1\}</tex>. Класс <tex dpi="130">H_{b,s}</tex> хеш-функций из <tex dpi="130">U</tex> в <tex dpi="130">\{0, \ldots, 2^s - 1\}</tex> определен как <tex dpi="130">H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex dpi="130">x</tex> из <tex dpi="130">U</tex>: <tex dpi="130">h_{a}(x) = (ax</tex> <tex dpi="130">\bmod</tex> <tex dpi="130">2^b)</tex> <tex dpi="130">div</tex> <tex dpi="130">2^{Леммаb - s}</tex>. Данный алгоритм базируется на [[#lemma1|idлемме №1]].  Взяв <tex dpi="130">s = 2 \log n</tex>, получаем хеш-функцию <tex dpi="130">h_{a}</tex>, которая захеширует <tex dpi="130">n</tex> чисел из <tex dpi="130">U</tex> в таблицу размера <tex dpi="130">O(n^2)</tex> без коллизий. Очевидно, что <tex dpi="130">h_{a}(x)</tex> может быть посчитана для любого <tex dpi="130">x</tex> за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить <tex dpi="130">h_{a}</tex> ко всему контейнеру, и в результате все хеш-значения для всех чисел в контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-значения вовлечены только (<tex dpi="130">\bmod</tex> <tex dpi="130">2^b</tex>) и (<tex dpi="130">div</tex> <tex dpi=lemma5"130">2^{b - s}</tex>).|statement Такая хеш-функция может быть найдена за <tex dpi="130">O(n^3)</tex>.Если принятьСледует отметить, что каждый контейнер содержит , несмотря на размер таблицы <tex dpi="130">O(n^2)</tex>logm , потребность в памяти не превышает <tex dpi="130"> lognO(n)</tex> , потому что хеширование используется только для уменьшения количества битв числе. ==Сортировка по ключу==Предположим, что <tex dpi="130">n</tex> чисел должны быть отсортированы, и в каждом <texdpi="130">g\log m</tex> бит. Будем считать, что в каждом числе есть <tex dpi="130">h</tex> чиселсегментов, в каждом из которых <texdpi="130">\log</tex> <tex dpi="150">\frac{m}{h}</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex dpi="130">2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex dpi="130">n</tex> чисел по <tex dpi="130">\log m</tex> бит в каждом стала задачей по сортировке <tex dpi="130">n</tex> чисел по <tex dpi="130">\log</tex> <tex dpi="150">\frac{m}{h}</tex> бит в каждом.  Также рассмотрим проблему последующего разделения. Пусть <tex dpi="130">a_{1}</tex>, <tex dpi="130">a_{2}</tex>, <tex dpi="130">\ldots</tex>, <tex dpi="130">a_{p}</tex> {{---}} <tex dpi="130">p</tex> чисел и <tex dpi="130">S</tex> {{---}} множество чисeл. Необходимо разделить <tex dpi="130">S</tex> в <tex dpi="130">p + 1</tex> наборов, таких, что: <tex dpi="130">S_{0} < a_{1} < S_{1} < a_{2} < \ldots < a_{p} < S_{p}</tex>. Так как используется '''сортировка по ключу''' (logmангл. ''signature sorting'')то перед тем, как делать вышеописанное разделение, необходимо поделить биты в <tex dpi="130">a_{i}</gtex> на <tex dpi="130">h</tex> сегментов и взять некоторые из них. Так же делим биты для каждого числа из <tex dpi="130">S</tex> и оставляем только один в каждом числе. По существу, для каждого <tex dpi="130">a_{i}</tex> берутся все <tex dpi="130">h</tex> сегментов. Если соответствующие сегменты <tex dpi="130">a_{i}</tex> и <tex dpi="130">a_{j}</tex> совпадают, то нам понадобится только один. Сегмент, который берется для числа в <tex dpi="130">S</tex> это сегмент, который выделяется из <tex dpi="130">a_{i}</tex>. Таким образом, начальная задача о разделении <tex dpi="130">n</tex> чисел по <tex dpi="130">\log m</tex> бит преобразуется в несколько задач на разделение с числами по <tex dpi="150">\frac{\log m}{h}</tex> бит.  '''Пример''':[[Файл:Han-example.png|500px|thumb]] <tex dpi="130">a_{1} = 3, a_{2} = 5, a_{3} = 7, a_{4} = 10, S = \{1, 4, 6, 8, 9, 13, 14\}</tex>. Делим числа на два сегмента. Для <tex dpi="130">a_{1}</tex> получим верхний сегмент <tex dpi="130">0</tex>, нижний <tex dpi="130">3</tex>; <tex dpi="130">a_{2}</tex> {{---}} верхний <tex dpi="130">1</tex>, нижний <tex dpi="130">1</tex>; <tex dpi="130">a_{3}</tex> {{---}} верхний <tex dpi="130">1</tex>, упакованы нижний <tex dpi="130">3</tex>; <tex dpi="130">a_{4}</tex> {{---}} верхний <tex dpi="130">2</tex>, нижний <tex dpi="130">2</tex>. Для элементов из S получим: для <tex dpi="130">1</tex> нижний <tex dpi="130">1</tex>, так как он выделяется из нижнего сегмента <tex dpi="130">a_{1}</tex>; для <tex dpi="130">4</tex> нижний <tex dpi="130">0</tex>; для <tex dpi="130">8</tex> нижний <tex dpi="130">0</tex>; для <tex dpi="130">9</tex> нижний <tex dpi="130">1</tex>; для <tex dpi="130">13</tex> верхний <tex dpi="130">3</tex>; для <tex dpi="130">14</tex> верхний <tex dpi="130">3</tex>. Теперь все верхние сегменты, нижние сегменты <tex dpi="130">1</tex> и <tex dpi="130">3</tex>, нижние сегменты <tex dpi="130">4, 5, 6, 7,</tex> нижние сегменты <tex dpi="130">8, 9, 10</tex> формируют <tex dpi="130">4</tex> новые задачи на разделение.   Использование '''сортировки по ключу''' в один контейнерданном алгоритме: Есть набор <tex dpi="130">T</tex> из <tex dpi="130">p</tex> чисел, которые отсортированы как <tex dpi="130">a_{1}, a_{2}, \ldots, a_{p}</tex>. Если каждое число имеет маркерИспользуем числа в <tex dpi="130">T</tex> для разделения набора <tex dpi="130">S</tex> из <tex dpi="130">q</tex> чисел <tex dpi="130">b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex dpi="130">p + 1</tex> наборов <tex dpi="130">S_{0}, S_{1}, \ldots, содержащий S_{p}</tex>. Пусть <tex dpi="150">h = \frac{\log n}{c \log p}</tex> для константы <tex dpi="130">c > 1</tex>. (logn<tex dpi="150">\frac{h}{\log\log n \log p}</tex>)-битные числа могут храниться в одном контейнере, содержащим <tex dpi="150">\frac{\log n}{c \log\log n}</tex> бит. Сначала рассматриваем биты в каждом <tex dpi="130">a_{i}</tex> и каждом <tex dpi="130">b_{i}</tex> как сегменты одинаковой длины <tex dpi="150">\frac{h} {\log\log n}</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах (2g)<tex dpi="130">a_{i}</tex>-ом и <tex dpi="130">b_{i}</tex> бит-ом) хешируются, и получается <texdpi="150">g\frac{h}{\log\log n}</tex> маркеров упакованы хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один . Пусть <tex dpi="130">a'_{i}</tex> {{---}} хеш-контейнер таким же образомдля <tex dpi="130">a_{i}</tex>, аналогично <tex dpi="130">b'_{i}</tex>. В сумме хеш-значения имеют <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит, хотя эти значения разделены на сегменты по <tex dpi="150">\frac{h}{ \log\log n}</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <texdpi="150">^*\frac{2 \log n}{c \log\log n}</tex>бит. Потом рассматривается каждый хеш-контейнер как число, что и числаэти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки биты в <tex dpi="130">a_{i}</tex> и <tex dpi="130">b_{i}</tex> разрезаны на <tex dpi="150">\frac{\log\log n}{h}</tex> сегментов. Таким образом, тогда получилось дополнительное мультипликативное преимущество (англ. ''additional multiplicative advantage'') в <texdpi="150">\frac{h} {\log\log n}</tex> чисел . После того, как вышеописанный процесс повторится <tex dpi="130">g</tex> раз, получится неконсервативное преимущество в <texdpi="150">(\frac{h} {\log\log n})^g</gtex> раз, в то время как потрачено только <tex dpi="130">O(gqt)</tex> контейнерах могут быть отсортированы по их маркерам времени, так как каждое многократное деление происходит за линейное время <texdpi="130">O(qt)</tex>.  Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, <tex dpi="150">\frac{\log\log n}{h}</tex>-ые, <tex dpi="150">(nloglogn\frac{\log\log n}{h})^2</gtex>-ые, <tex dpi="130">\ldots</tex> по счету в числе. Хеш-функцию для <tex dpi="150">(\frac{\log\log n}{h})^t</tex>-ых по счету сегментов, получаем нарезанием всех <tex dpi="130">p</tex> с использованием чисел на <texdpi="150">O(\frac{\log\log n}{h})^t</gtex> сегментов. Рассматривая каждый сегмент как число, получаем <tex dpi="150">p(\frac{\log\log n}{h})^t</tex> местачисел. Затем получаем одну хеш-функцию для этих чисел. Так как <tex dpi="130">t < \log n</tex>, то получится не более <tex dpi="130">\log n</tex> хеш-функций.  Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит. Есть <tex dpi="130">t</tex> наборов, в каждом из которых <tex dpi="130">q + p</tex> хешированных контейнеров по <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит в каждом. Эти контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.  Операция '''сортировки за линейное время''' (*англ. ''Linear-Time-Sort'') Входные данные: если число <texdpi="150">r \geqslant n^{\frac{2}{5}}</tex> чисел <tex dpi="130">d_{i}</tex>, <tex dpi="130">d_{i}.value</tex> — значение числа <tex dpi="130">d_{i}</tex>, в котором <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит, <tex dpi="130">d_{i}.set</tex> — набор, в котором находится <tex dpi="130">d_{i}</tex>. Следует отметить, что всего есть <tex dpi="130">t</tex> наборов. # Сортируем все <tex dpi="130">d_{i}</tex> по <tex dpi="130">d_{i}.value</tex>, используя bucket sort. Пусть все отсортированные числа в <tex dpi="130">aA[1..r]</tex> упаковано . Этот шаг занимает линейное время, так как сортируется не менее <tex dpi="150">n^{\frac{2}{5}}</tex> чисел.# Помещаем все <tex dpi="130">A[j]</tex> в <tex dpi="130">A[j].set</tex>. ==Сортировка с использованием O(n log log n) времени и памяти==Для сортировки <texdpi="130">sn</tex>целых чисел в диапазоне <tex dpi="130">\{0, 1, \ldots, m -ое число 1\}</tex> предполагается, что в нашем консервативном алгоритме используется контейнер длины <tex dpi="130">O(\log (m + n))</tex>. Далее везде считается, что все числа упакованы в контейнеры одинаковой длины.   Берем <tex dpi="130">1/e = 5</tex>tдля ЭП-дерева Андерссона. Следовательно, у корня будет <tex dpi="150">n^{\frac{1}{5}}</tex>детей, и каждое ЭП-ом контейнере для дерево в каждом ребенке будет иметь <tex dpi="150">n^{\frac{4}{5}}</tex> листьев. В отличие от оригинального дерева, за раз вставляется не один элемент, а <tex dpi="130">d^2</tex>, где <tex dpi="130">d</tex> — количество детей узла дерева, в котором числа должны спуститься вниз. Алгоритм полностью опускает все <tex dpi="130">d^2</tex> чисел на один уровень. В корне опускаются <tex dpi="150">n^{\frac{2}{5}}</tex> чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на <tex dpi="130">t_{1} = n^{1/5}</tex> наборов <tex dpi="130">S_{1}, S_{2}, \ldots, S_{t_{1}}</tex>, в каждом из которых <tex dpi="150">n^{\frac{4}{5}}</tex> чисели <tex dpi="130">S_{i} < S_{j}, тогда маркер для i < j</tex>. Затем, берутся <texdpi="150">an^{\frac{8}{25}}</tex> упакован как чисел из <texdpi="130">sS_{i}</tex>и опускаются на следующий уровень ЭП-ый маркер дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <tex dpi="150">t_{2} = n^{\frac{1}{5}}n^{\frac{4}{25}} = n^{\frac{9}{25}}</tex> наборов <tex dpi="130">T_{1}, T_{2}, \ldots, T_{t_{2}}</tex>, аналогичных наборам <tex dpi="130">S_{i}</tex>, в каждом из которых <texdpi="150">tn^{\frac{16}{25}}</tex>чисел. Теперь числа опускаются дальше в ЭП-ом контейнере для маркеровдереве.|proofНетрудно заметить, что перебалансирока занимает <tex dpi="130">O(n \log\log n)</tex> времени с <tex dpi="130">O(n)</tex> времени на уровень, аналогично стандартному ЭП-дереву Андерссона. Контейнеры для маркеров могут быть отсортированы Нам следует нумеровать уровни ЭП-дерева с помощью bucket sort потомукорня, что начиная с нуля. Рассмотрим спуск вниз на уровне <tex dpi="130">s</tex>. Имеется <tex dpi="150">t = n^{1 - (\frac{4}{5})^S}</tex> наборов по <tex dpi="150">n^{(\frac{4}{5})^S}</tex> чисел в каждом. Так как каждый контейнер использует узел на данном уровне имеет <texdpi="150">p = n^{\frac{1}{5} \cdot (logn\frac{4}{5})^S}</tex> детей, то на <tex dpi="130">s + 1</tex> уровень опускаются <tex dpi="150">q = n^{\frac{2}{5} \cdot (\frac{4}{5})^S}</tex> бит. Сортировка сгруппирует контейнеры чисел для каждого набора, или всего <tex dpi="150">qt \geqslant n^{\frac{2}{5}}</tex> чисел для всех наборов за один раз.  Спуск вниз можно рассматривать как сортировку <tex dpi="130">q</tex> чисел в четвертой леммекаждом наборе вместе с <tex dpi="130">p</tex> числами <tex dpi="130">a_{1}, a_{2}, \ldots, a_{p}</tex> из ЭП-дерева, так, что эти <tex dpi="130">q</tex> чисел разделены в <tex dpi="130">p + 1</tex> наборов <tex dpi="130">S_{0}, S_{1}, \ldots, S_{p}</tex> таких, что <tex dpi="130">S_{0} < a_{1} < \ldots < a_{p} < S_{p}</tex>.  Так как <tex dpi="130">q</tex> чисел не надо полностью сортировать и <tex dpi="130">q = p^2</tex>, то можно использовать [[#lemma6|лемму №6]] для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с помощью [[Сортировка Хана#Signature sorting|signature sorting]]. Для этого используется линейная техника многократного деления (англ. ''multi-dividing technique'').  После <tex dpi="130">g</tex> сокращений бит в [[Сортировка Хана#Signature sorting|signature sorting]] получаем неконсервативное преимущество в <tex dpi="150">(\frac{h}{ \log\log n})^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переместить каждую группу контейнеров переключиться на [[#lemma6|лемму №6]] для завершения разделения <tex dpi="130">q</tex> чиселс помощью <tex dpi="130">p</tex> чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex dpi="130">w</tex> подзадач разделения на <tex dpi="130">w</tex> поднаборов для какого-то числа <tex dpi="130">w</tex>.  Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя [[#lemma6|лемму №6]], делается разделение. Так как получено неконсервативное преимущество в <tex dpi="150">(\frac{h}{\log\log n})^g</tex> и работа происходит на уровнях не ниже, чем <tex dpi="130">2 \log\log\log n</tex>, то алгоритм занимает <tex dpi="150">O(\frac{qt \log\log n}{g(\log h - \log\log\log n) - \log\log\log n}) = O(\log\log n)</tex> времени.  ЗаметимВ итоге разделились <tex dpi="130">q</tex> чисел <tex dpi="130">p</tex> числами в каждый набор. То есть получилось, что <tex dpi="130">S_{0} < e_{1} < S_{1} < \ldots < e_{p} < S_{p}</tex>, где <tex dpi="130">e_{i}</tex> {{---}} сегмент <tex dpi="130">a_{i}</tex>, полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, что числа хранятся в массиве <tex dpi="130">B</tex> так, что сортирующие алгоритмы числа в четвертой <tex dpi="130">S_{i}</tex> предшествуют числам в <tex dpi="130">S_{j}</tex> если <tex dpi="130">i < j</tex> и пятой леммах нестабильные<tex dpi="130">e_{i}</tex> хранится после <tex dpi="130">S_{i - 1}</tex>, но до <tex dpi="130">S_{i}</tex>.   Пусть <tex dpi="130">B[i]</tex> находится в поднаборе <tex dpi="130">B[i]. Хотя на их основе можно построить стабильные алгоритмы используя известный метод добавления адресных битов к каждому входящему числуsubset</tex>. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все <tex dpi="130">B[j]</tex> в <tex dpi="130">B[j].subset</tex>. На это потребуется линейное время и место. 

Если у нас длина Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex dpi="130">\log m \geqslant \log\log\log n</tex>, потому что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex dpi="150">\frac{h}{\log\log n}</tex> хешированных значений (сегментов) в себе на уровне <tex dpi="130">\log h</tex> в ЭП-дереве. Полное число хешированных бит в контейнере равно <tex dpi="130">(2 \log n)(c \log\log n)</tex> бит. Хешированные биты в контейнере выглядят как <tex dpi="130">0^{i}t_{1}0^{i}t_{2} \ldots t</tex><tex dpi="150">_{\frac{h}{\log\log n}}</tex>, где <tex dpi="130">t_{k}</tex>-ые — хешированные биты, а нули {{---}} это просто нули. Сначала упаковываем <tex dpi="130">\log\log n</tex> контейнеров большев один и получаем <tex dpi="130">w_{1} = 0^{j}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, сортировка может быть ускорена1}0^{j}t_{1, как показано 2} \ldots t_{\log\log n,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex>, где <tex dpi="130">t_{i, k}</tex>: элемент с номером <tex dpi="130">k = 1, 2, \ldots, </tex><tex dpi="150">\frac{h}{\log\log n}</tex> из <tex dpi="130">i</tex>-ого контейнера. Используем <tex dpi="130">O(\log\log n)</tex> шагов, чтобы упаковать <tex dpi="130">w_{1}</tex> в <tex dpi="130">w_{2} = 0</tex><tex dpi="150">^{\frac{jh}{\log\log n}}</tex><tex dpi="130">t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}t_{1, 2}t_{2, 2} \ldots t_{1,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex><tex dpi="130">t_{2,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex><tex dpi="130">\ldots t_{\log\log n,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex>. Теперь упакованные хеш-биты занимают <tex dpi="130">2 \log</tex><tex dpi="150">\frac{n}{c}</tex> бит. Используем <tex dpi="130">O(\log\log n)</tex> времени чтобы распаковать <tex dpi="130">w_{2}</tex> в <tex dpi="130">\log\log n</tex> контейнеров <tex dpi="130">w_{3, k} = 0</tex><tex dpi="150">^{\frac{jh}{\log\log n}}</tex><tex dpi="130">0^{r}t_{k, 1}0^{r}t_{k, 2} \ldots t_{k,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex> <tex dpi="130">k = 1, 2, \ldots, \log\log n</tex>. Затем, используя <tex dpi="130">O(\log\log n)</tex> времени, упаковываем эти <tex dpi="130">\log\log n</tex> контейнеров в один <tex dpi="130">w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} \ldots t_{1,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex><tex dpi="130">0^{r}t_{2, 1} \ldots t_{\log\log n,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex>. Затем, используя <tex dpi="130">O(\log\log n)</tex> шагов, упаковываем <tex dpi="130">w_{4}</tex> в следующей лемме<tex dpi="130">w_{5} = 0^{s}t_{1, 1}t_{1, 2} \ldots t_{1,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex><tex dpi="130">t_{2, 1}t_{2, 2} \ldots t_{\log\log n,}</tex><tex dpi="150">_{ \frac{h}{\log\log n}}</tex>. В итоге используется <tex dpi="130">O(\log\log n)</tex> времени для упаковки <tex dpi="130">\log\log n</tex> контейнеров. Считаем, что время, потраченное на один контейнер — константа.

Лемма шесть.{{Лемма|id=lemma6=См.|statementтакже=предположим, что каждый контейнер содержит <tex>logmloglogn > logn</tex> бит, что <tex>g</tex> чисел, в каждом из которых <tex>(logm)/g</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>(logn)/(2g)</tex> бит, и что <tex>g</tex> маркеров упакованы в один контейнер тем же образом что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(n/g)</tex>, с использованием <tex>O(n/g)</tex> памяти.|proof=Заметим, что несмотря на то, что длина контейнера <tex>logmloglogn</tex> бит всего <tex>logm</tex> бит используется для хранения упакованных чисел. Так же как в леммах четыре и пять мы сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел мы помещаем <tex>gloglogn</tex> вместо <tex>g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе содержащей <tex>gloglogn</tex> контейнеров мы сначала упаковываем <tex>gloglogn</tex> контейнеров в <tex>g</tex> контейнеров упаковывая <tex>loglogn</tex> контейнеров в один. Далее мы делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего <tex>O(gloglogn)</tex> времени для каждой группы и <tex>O(n/g)</tex> времени для всех чисел. После завершения транспозиции, мы далее распаковываем <tex>g</tex> контейнеров в <tex>gloglogn</tex> контейнеров.* [[Сортировка подсчетом]]}}* [[Цифровая сортировка]]

Заметим, что если длина контейнера <tex>logmloglogn<==Источники информации==* [http://www.sciencedirect.com/science/tex> и только <tex>logm<article/tex> бит используется для упаковки <tex>g <= logn<pii/tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>S019667740300155X Deterministic Sorting in O(n/glog log n) Time and Linear Space. Yijie Han.]* А. Андерссон. Fast deterministic sorting and searching in linear space. Proc. 1996 IEEE Symp. on Foundations of Computer Science. 135-141(1996)<* [http:/tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)<dl.acm.org/tex>citation.cfm?id=1236460 A. Andersson, M. Thorup. Dynamic ordered sets with exponential search trees.]* [[wikipedia:en:Integer_sorting|Wikipedia {{---}} Integer sorting]]

==Сортировка <tex>n</tex> целых чисел в <tex>\sqrt{n}</tex> наборов==Постановка задачи [[Категория: Дискретная математика и решение некоторых проблем:алгоритмы]]

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