Изменения

'''Сортировка Хана ''' (Yijie Han)англ. ''Hansort'' ) {{---}} сложный алгоритм сортировки целых чисел со сложностью <texdpi="130">O(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> (<tex>0< e < 1</tex>) ЭП-поддеревьев, в каждом из которых <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> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

{{Определение|definition ==Определения== # Контейнер '''ЭП-дерево''' {{---}} объектэто дерево поиска, в которым котором все ключи хранятся наши данные. Например: 32-битные в листьях этого дерева и 64-битные числа, массивы, вектораколичество детей у каждого узла уменьшается экспоненциально от глубины узла.# Алгоритм сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> называется консервативным, если длина контейнера (число бит в контейнере), является <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм неконсервативный.# Если сортируются целые числа из множества <tex>\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\ge</tex> 1, тогда сортировка происходит с неконсервативным преимуществом <tex>k</tex>.# Для множества <tex>S</tex> определим

Набор 1) Корень имеет <texdpi="130">S1\Theta (n^e)</tex> < сыновей <texdpi="130">S2( 0 </tex> если e <tex>\max(S1) \le \min(S21 )</tex>. Все сыновья являются ЭП-деревьями.

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

==Определения== {{ Определение | definition = '''Контейнер''' {{---}} объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.}}{{ Определение | definition = Алгоритм: Пусть целое число , сортирующий <texdpi="130">b \ge 0n</tex> и пусть целых чисел из множества <texdpi="130">U = \{0, 1, \ldots, 2^b m - 1\}</tex>. Класс , называется '''консервативным''', если длина контейнера (число бит в контейнере) равна <texdpi="130">H_{b,s}O(\log(m + n))</tex> хеш функций . Если длина больше, то алгоритм '''неконсервативный'''. }}{{ Определение | definition = Если сортируются целые числа из множества <tex>U</tex> в <texdpi="130">\{0, 1, \ldots, 2^s m - 1\}</tex> определен как с длиной контейнера <texdpi="130">H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a k \equiv 1 log (\bmod 2m + n)\}</tex> и для всех <tex>x</tex> из с <tex>U: h_{a}(x) dpi= (ax</tex> <tex"130">k \bmodgeqslant 1</tex> , тогда сортировка происходит с '''неконсервативным преимуществом''' <texdpi="130">2^b)k</tex> .}}{{ Определение | definition = Для множества <texdpi="130">divS</tex> определим <texdpi="130">2^\min(S) = \min\limits_{b - sa \in S}a</tex>.

Данный алгоритм базируется на <btex dpi="130">лемме №1\max(S) = \max\limits_{a \in S} a</btex>

Взяв {{ Определение | definition = Предположим, есть набор <texdpi="130">s = 2 \log nT</tex> получаем хеш функцию из <texdpi="130">h_{a}p</tex> которая захеширует чисел, которые уже отсортированы как <texdpi="130">na_{1}, a_{2}, \ldots, a_{p}</tex> чисел из и набор <texdpi="130">US</tex> в таблицу размера из <texdpi="130">O(n^2)q</tex> без коллизий. Очевидно, что чисел <texdpi="130">h_b_{1}, b_{2}, \ldots, b_{aq}(x)</tex> может быть посчитана для любого . Тогда '''разделением''' <texdpi="130">xq</tex> за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, спокойно применяется <texdpi="130">h_{a}p</tex> ко всему контейнеру, а в результате все хеш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хеш знчения вовлечены только (числами называется <texdpi="130">\bmodp + 1</tex> набор <texdpi="130">2^bS_{0}, S_{1}, \ldots, S_{p}</tex>) и (, где <texdpi="130">divS_{0} < a_{1} < S_{1} < \ldots </tex> a_{p} <tex>2^S_{b - sp}</tex>). }}

Такая хеш функция {{Лемма|id = lemma1|about = № 1|statement = Даны целые числа <tex dpi="130">b \geqslant s \geqslant 0</tex>, и <tex dpi="130">T</tex> является подмножеством множества <tex dpi="130">\{0, \ldots, 2^b - 1\}</tex>, содержащим <tex dpi="130">n</tex> элементов, и <tex dpi="130">t \geqslant 2^{-s + 1}С^k_{n}</tex>. Функция <tex dpi="130">h_{a}</tex>, принадлежащая <tex dpi="130">H_{b,s}</tex>, может быть найдена выбрана за время <texdpi="130">O(nbn^32)</tex> так, что количество коллизий <tex dpi="130">coll(h_{a}, T)\leqslant t</tex>.}}

Следует отметить|proof = Так как возможно делать попарное сравнение <tex dpi="130">g</tex> чисел в одном контейнере с <tex dpi="130">g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <tex dpi="130">\ldots</tex>, что несмотря на размер таблицы <texdpi="130">O(n^2)g</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, потребность набор <tex dpi="130">S</tex> из медиан теперь содержится в памяти не превышает <texdpi="150">O(\frac{n)}{5g}</tex> контейнерах. Рекурсивно находим медиану <tex dpi="130">m</tex> в <tex dpi="130">S</tex>. Используя <tex dpi="130">m</tex> потому, что хеширование используется только для уменьшения количества бит уберем хотя бы <tex dpi="150">\frac{n}{4}</tex> чисел среди <tex dpi="130">n</tex>. Затем упакуем оставшиеся из <tex dpi="150">\frac{n}{g}</tex> контейнеров в числе<tex dpi="150">\frac{3n}{4g}</tex> контейнеров и затем продолжим рекурсию.}}

{{Лемма|id =lemma3|about =Собственно сортировка с использованием O(nloglogn) времени и памяти=№ 3|statement =Для сортировки Если <texdpi="130">ng</tex> целых чисел , в диапазоне от сумме использующих <tex dpi="150">\frac{\log n}{2}</tex>0бит, 1упакованы в один контейнер, тогда <tex dpi="130">n</tex> чисел в <tex dpi="150">\ldots, m - 1frac{n}{g}</tex>} предполагается, что используем контейнер длины контейнерах могут быть отсортированы за время <texdpi="150">O(\frac{n \log g}{g})</tex> с использованием <tex dpi="150">O(m + \frac{n)}{g})</tex> в нашем консервативном алгоритме. Далее всегда считается, что все числа упакованы в контейнеры одинаковой длиныпамяти.

Берем |proof = Так как используется только <texdpi="150">1\frac{\log n}{2}</e tex> бит в каждом контейнере для хранения <tex dpi= 5"130">g</tex> для экспоненциального поискового дереве Андерссона. Поэтому у корня будет чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает <texdpi="150">O(\frac{n^}{1/5g})</tex> детей времени и каждое ЭП-дерево в каждом ребенке будет иметь памяти. Так как используется <texdpi="150">\frac{\log n^}{4/52}</tex> листьев. В отличии от оригинального деревабит на контейнер, вставляется не один элемент за раз, а понадобится <texdpi="130">d^2\sqrt{n}</tex>, где шаблонов для всех контейнеров. Затем поместим <texdpi="150">dg < \frac{\log n}{2}</tex> {{---}} количество детей узла дерева, где числа должны спуститься внизконтейнеров с одинаковым шаблоном в одну группу. Алгоритм полностью опускает все Для каждого шаблона останется не более <texdpi="130">d^2g - 1</tex> чисел на один уровеньконтейнеров, которые не смогут образовать группу. В корне опускаются Поэтому не более <texdpi="130">\sqrt{n^{2/5}(g - 1)</tex> чисел на следующий уровеньконтейнеров не смогут сформировать группу. После того, как опустились все числа на следующий уровень и они успешно разделились на Для каждой группы помещаем <texdpi="130">t_{1} = n^{1/5}i</tex> наборов -е число во всех <texdpi="130">S_{1}, S_{2}, \ldots, S_{t_{1}}g</tex>, контейнерах в каждом из которых один. Таким образом берутся <texdpi="130">n^{4g</5}tex> <tex dpi="130">g</tex> чисел -целых векторов и получаются <texdpi="130">S_{i} g< S_{j}, i /tex> < jtex dpi="130">g</tex>. Затем-целых векторов, берутся где <texdpi="130">n^{(4/5)(2/5)}i</tex> чисел из -ый вектор содержит <texdpi="130">S_{i}</tex> и за раз и опускаются на следующий уровень ЭП-дереваое число из входящего вектора. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на Эта транспозиция может быть сделана за время <texdpi="130">t_{2} = n^{1/5}n^{4/25} = n^{9/25}O(g \log g)</tex> наборов , с использованием <texdpi="130">T_{1}, T_{2}, \ldots, T_{t_{2}}O(g)</tex> в каждом из которых памяти. Для всех групп это занимает время <texdpi="150">O(\frac{n^\log g}{16/25g})</tex> чисел, аналогичным наборам с использованием <texdpi="150">S_O(\frac{in}{g})</tex>. Теперь числа опускаются дальше в ЭП-деревепамяти.

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

Спуск вниз можно рассматривать как сортировку <tex>q</tex> чисел в каждом наборе вместе |proof = Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <texdpi="150">p</tex> числами <tex>a_\frac{1\log n}, a_{2}, \ldots, a_{p}</tex> из ЭП-дерева, так, что эти <tex>q</tex> бит. Сортировка сгруппирует контейнеры для чисел разделены как в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1[[#lemma3|лемме №3]]. Перемещаем каждую группу контейнеров для чисел.}, \ldots, S_{p}</tex> таких, что <tex>S_{0} < </tex>{<tex>a_{1}</tex>} < <tex>\ldots</tex> < {<tex>a_{p}</tex>}<tex> < S_{p}</tex>

|proof = Заметим, что несмотря на то, что длина контейнера <tex dpi="130">\log m \log\log n</tex> бит, всего <tex dpi="130">\log m</tex> бит используется для хранения упакованных чисел. Так же как не надо полностью сортировать в [[#lemma3|лемме №3]] и [[#lemma4|лемме №4]] сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем <texdpi="130">g \log\log n</tex> вместо <tex dpi="130">qg</tex> контейнеров чисел в одну группу. Для транспозиции чисел и в группе, содержащей <tex dpi="130">g \log\log n</tex> контейнеров, упаковываем <tex dpi="130">g \log\log n</tex>q контейнеров в <tex dpi= p^2"130">g</tex>, то есть возможность использовать лемму 2 для сортировкиупаковывая <tex dpi="130">\log\log n</tex> контейнеров в один. Для этого необходимо неконсервативное преимущество, которое получается нижеДалее делаем транспозицию над <tex dpi="130">g</tex> контейнерами. Для этого используется линейная техника многократного деления Таким образом перемещение занимает всего <tex dpi="130">O(g \log\log n)</tex> времени для каждой группы и <tex dpi="150">O(multi-dividing technique\frac{n}{g})</tex> времени для всех чисел. После завершения транспозиции, чтобы добиться этогораспаковываем <tex dpi="130">g</tex> контейнеров в <tex dpi="130">g \log\log n</tex> контейнеров.

Для этого воспользуемся signature sorting. Адаптируем этот алгоритм для нас. Предположим у нас есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex>, и хотется использовать числа в <tex>T</tex> для разделения <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}Заметим, \ldots, S_{p}</tex> что если длина контейнера <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами. Пусть <tex>h dpi= \log n/(c \log p)</tex"130"> для константы <tex>c > 1</tex>. <tex>h/ \log\log n \log p</tex> битные числа могут быть хранены в одном контейнере, так что одно слово хранит <tex>(\log n)/(c m \log\log n)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины только <texdpi="130">h/ \log\log nm</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество бит используется для сортировки, хешируются числа в этих контейнерах (<tex>a_{i}</tex>-ом и упаковки <texdpi="130">b_{i}</tex>-ом), чтобы получить <tex>h/ g \logleqslant \log n</tex> хешированных значений чисел в одном контейнере. Чтобы получить значения сразу, при вычислении хеш значений сегменты не влияют друг на другаодин контейнер, можно даже отделить четные и нечетные сегменты тогда выбор в два контейнера. Не умаляя общности считаем, что хеш значения считаются [[#lemma2|лемме №2]] может быть сделан за константное время. Затем, посчитав значения, два контейнера объединяются в один. Пусть и память <texdpi="150">a'_O(\frac{in}</tex> хеш контейнер для <tex>a_{ig}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хеш значения имеют <tex>(2 \log n)/(c \log\log n)</tex> бит. Хотя эти значения разделены на сегменты по <tex>h/ \log\log n</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты потому что упаковка в доказательстве [[#lemma2|лемме №2]] теперь может быть сделана за время <texdpi="150">O(2 \log n)/(c \log\log frac{n}{g})</tex> бит. Потом рассматриваются каждый хеш контейнер как число и сортируются эти хеш контейнеры за линейное время (сортировка рассмотрена чуть позже). После этой сортировки биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>\log\log n/h</tex>. Таким образом получилось дополнительное мультипликативное преимущество в <tex>h/ \log\log n</tex> (additional multiplicative advantage).

После того{{Лемма|id = lemma6|about = № 6|statement = <tex dpi="130">n</tex> целых чисел можно отсортировать в <tex dpi="130">\sqrt{n}</tex> наборов <tex dpi="130">S_{1}</tex>, как повторится вышеописанный процесс <texdpi="130">gS_{2}</tex> раз, получится неконсервативное преимущество в <texdpi="130">(h\ldots</ tex>, <tex dpi="130">S_{\logsqrt{n}}</tex> таким образом, что в каждом наборе <tex dpi="130">\log sqrt{n)^g}</tex> чисел и <tex dpi="130">S_{i} < S_{j}</tex> при <tex dpi="130">i < j</tex> раз, в то за время, как потрачено только <texdpi="150">O(gqt\frac{n \log\log n} {\log k})</tex> времени, так как каждое многократное деление делятся за линейное время и место <texdpi="130">O(qtn)</tex> с неконсервативным преимуществом <tex dpi="130">k \log\log n</tex>.

Хеш функция, которая используется, находится следующим образом. Будут хешироватся сегменты, которые <tex>\log\log n/h</tex>-ые, <tex>(\log\log n/h)^2</tex>-ые, <tex>\ldots</tex> от всего числа. Для сегментов вида |proof = Алгоритм сортировки <texdpi="130">(\log\log n/h)^t</tex>, получаем нарезанием всех <tex>p</tex> целых чисел на в <texdpi="130">(\log\log sqrt{n/h)^t}</tex> сегментов. Рассматривая каждый сегмент как числонаборов, получится <tex>p(\log\log n/h)^t</tex> чисел. Затем получаем одну хеш функцию для этих чисел. Так как <tex>t < \log n</tex> топредставленный ниже, получится не более <tex>\log n</tex> хеш функцийявляется доказательством данной леммы.

Входные данныеНа каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.), потому что каждое м.ч. теперь содержит только <tex dpi="150">\frac{\log m}{\log n}</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер <tex dpi="130">\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex dpi="150">\frac{n}{\log n}</tex> контейнеров с <tex dpi="130">\log n</tex> м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на эту упаковку, считаем, что она бесплатна. По [[#lemma2|лемме №2]] находим медиану этих <tex dpi="130">n</tex> м.ч. за время и память <tex dpi="150">O(\frac{n}{\log n})</tex>. Пусть <tex dpi="130">a</tex> {{---}} это найденная медиана. Тогда <tex dpi="130">n</tex> м.ч. могут быть разделены на не более чем три группы: <texdpi="130">r S_{1}</tex> , <tex dpi= n^"130">S_{2}</tex> и <tex dpi="130">S_{3}</tex>. <tex dpi="130">S_{1}</tex> содержит м.ч., которые меньше <tex dpi="130">a</5tex>, <tex dpi="130">S_{2}</tex> чисел содержит м.ч., равные <tex dpi="130">a</tex>, <texdpi="130">d_S_{i3}</tex>содержит м.ч., большие <tex dpi="130">a</tex>. Также мощность <tex dpi="130">S_{1}</tex> и <tex dpi="130">S_{3} </tex> не превосходит <tex dpi="130">n/2</tex>. Мощность <texdpi="130">d_S_{i2}</tex>может быть любой.value значение числа Пусть <texdpi="130">d_S'_{i2}</tex> {{---}} это набор чисел, у которых наибольший блок находится в котором <texdpi="130">(S_{2 }</tex>. Тогда убираем из дальнейшего рассмотрения <tex dpi="150">\log n)/(c frac{\logm}{\log n)}</tex> бит(наибольший блок) из каждого числа, принадлежащего <texdpi="130">d_S'_{i2}</tex>. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения.setТак как в каждом числе только <tex dpi="130">\log n</tex> блоков, для каждого числа потребуется не более <tex dpi="130">\log n</tex> наборстадий, чтобы поместить его в котором находится набор половинного размера. За <tex dpi="130">2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <texdpi="150">d_\frac{n}{i\log n}</tex>контейнерами, то игнорируя время, следует отметить что всего необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается <tex dpi="130">O(n)</tex>tвремени из-за <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> блоков, каждое м.ч. может содержать <tex dpi="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> м.ч., в каждом из которых <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>.

Теперь для каждого набора собираются все его поднаборы Рассмотрим число <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>(hназовем это <tex dpi="130">a''</ \log\log ntex>)^gв <tex dpi="130">S</tex> и работа происходит , <tex dpi="130">a''</tex> просто перемещен на уровнях позицию в наборе <tex dpi="130">S</tex>, но не ниже чем обязательно на позицию <tex dpi="130">i</tex>2 \log\log\log n(где расположен <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>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, последующие блоки помещаются в набор вместе с текущим блоком. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <texdpi="130">O(qt k \log\log ne</(g(\log h tex> блоков {{-- \log\log\log n) - }} это текущий блок. Таким образом, после того, как эти <tex dpi="130">k \loge</tex> блоков помещены в набор, изначальный текущий блок удаляется, потому что известно, что эти <tex dpi="130">k \log\log n)) e</tex> блоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex dpi= O("130">k \log\log n)e</tex> времениблоках.

В итоге разделились <tex>q</tex> чисел <tex>p</tex> числами в каждый набор. То есть, получилосьСтоит отметить, что <tex>S_{0}</tex> < {<tex>e_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>e_{p}</tex>} < <tex>S_{p}</tex>, где <tex>e_{i}</tex> это сегмент <tex>a_{i}</tex> полученный с помощью битового сокращенияпосле нескольких уровней деления размер наборов станет маленьким. Такое разделение получилось комбинированием всех поднаборов в подзадачах. ПредполагаемЛеммы [[#lemma3|3]], что числа хранятся в массиве <tex>B</tex> так[[#lemma4|4]], что числа в [[#lemma5|5]] расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <texdpi="130">S_{i}n</tex> предшествуют числам элементов в наборы размера <texdpi="130">S_\sqrt{jn}</tex> если <tex>i < j</tex> и <tex>e_{i}</tex> хранится после <tex>S_{i - 1}</tex> но до <tex>S_{i}</tex>. Пусть <tex>B[i]</tex> в поднаборе <tex>B[i].subset</tex>. Чтобы позволить разделению выполнится для каждого поднабора делается следующее, то проблем быть не должно.

Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex>\log m \ge \log\log\log n</tex>, потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/ \log\log nadvantage</tex> хешированных значений (сегментов) в себе на уровне <tex>\log h</tex> в ЭП-дереве. Полное число хешированных бит в контейнере <tex>(2 \log n)(c \log\log n)</tex> бит. Хотя хешированны биты в контейнере выглядят как <tex>0^{i}t_{1}0^{i---}t_{2} \ldots t_{h/ \log\log n}</tex>, где это неконсервативное преимущество равное <tex>t_{k}</tex>-ые это хешированные биты, а нули это просто нули. Сначала упаковываем <tex>\log\log n</tex> контейнеров в один и получаем <tex>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, h/ \log\log n}</tex> где <tex>t_a_{i, k}</tex>: <tex>k = 1, 2, \ldots, h/ \log\log n</tex> из <tex>i</tex>-ого контейнера. Ипользуем <tex>O(\log\log n)</tex> шагов, чтобы упаковать <tex>w_{1}</tex> ые это входящие целые числа в <tex>w_{2} = 0^{jh/ \log\log n}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}t_{1, 2}t_{2, 2} \ldots t_{1, h/ \log\log n}t_{2наборе, h/ \log\log n} \ldots t_{\log\log nкоторые надо отсортировать, h/ \log\log n}</tex>. Теперь упакованные хеш биты занимают <tex>2 \log n/clevel</tex> бит. Используем <tex>O(\log\log n)</tex> времени чтобы распаковать <tex>w_{2}</tex> в <tex>\log\log n</tex> контейнеров <tex>w_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, 1}O^{r}t_{k, 2} \ldots t_{k, h/ \log\log n} k = 1, 2, \ldots, \log\log n</tex>. Затем используя <tex>O(\log\log n)</tex> времени упаковываем эти <tex>\log\log n</tex> контейнеров в один <tex>w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} \ldots t_{1, h/ \log\log n}0^{r}t_{2, 1} \ldots t_{\log\log n, h/ \log\log n}</tex>. Затем используя <tex>O(\log\log n)</tex> шагов упаковать <tex>w_{4}</tex> в <tex>w_{5} = 0^{s}t_{1, 1}t_{1, 2} \ldots t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} \ldots t_{\log\log n, h/ \log\log n}</tex>. В итоге используем <tex>O(\log\log n)</tex> времени для упаковки <tex>\log\log n</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>-ых номеров контейнеров. Где <tex dpi="130">a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex dpi=Signature sorting"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>, показывающее на текущий блок в нем, так же направлено назад к <tex dpi="130">a_{i}</tex>.## Отправляем <tex dpi="130">a_{i}</tex>-ые к их наборам, используя [[#lemma5|лемму №5]].

Предположим, что от 1 до 5# Помещаем <texdpi="130">na_{i}</tex> чисел должны быть сортированыв соответствующий набор с помощью блочной сортировки (англ. ''bucket sort''), и в каждом потому что наборов около <texdpi="130">\log msqrt{n}</tex> бит. Рассматривается, что в каждом числе есть # Для каждого набора <texdpi="130">hS = </tex> сегментов, в каждом из которых {<texdpi="130">a_{i_{0}}, a_{i_{1}}, \log (m/h)ldots, a_{i_{t}}</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем }, если <texdpi="130">t >2h \log sqrt{n}</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке , вызываем <tex>nSort(advantage</tex> чисел по <tex>m</tex> бит в каждом стала задачей по сортировке , <texdpi="130">\log_{k}(\frac{\log n}{4})</tex> чисел по , <texdpi="130"> a_{i_{0}}, a_{i_{1}}, \log (m/h)ldots, a_{i_{t}}</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>. Для Класс <texdpi="130">a_H_{1b,s}</tex> получим верхний сегмент хеш-функций из <tex dpi="130">U</tex> в <tex dpi="130">\{0, нижний 3; \ldots, 2^s - 1\}</tex> определен как <texdpi="130">a_H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> верхний 1, нижний 1; и для всех <tex dpi="130">x</tex> из <tex dpi="130">U</tex>: <texdpi="130">a_h_{3a}(x) = (ax</tex> верхний 1, нижний 3; <texdpi="130">a_{4}\bmod</tex> верхний <tex dpi="130">2, нижний 2. Для элементов из S получим: для 1: нижний 1 т.к. он выделяется из нижнего сегмента ^b)</tex> <tex dpi="130">div</tex> <texdpi="130">a_2^{1b - s}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.

==Лемма Данный алгоритм базируется на [[#lemma1|лемме №1==Даны целые числа <tex>b</tex> <tex>\ge</tex> <tex>s</tex> <tex>\ge</tex> 0 и <tex>T</tex> является подмножеством <tex>\{0, \ldots, 2^b - 1\}</tex>, содержащим <tex>n</tex> элементов, и <tex>t</tex> <tex>\ge</tex> <tex>2^{-s + 1}</tex>С<tex>^k_{n}</tex>]]. Функция <tex>h_{a}</tex> принадлежащая <tex>H_{b,s}</tex> может быть выбрана за время <tex>O(bn^2)</tex> так, что количество коллизий <tex>coll(h_{a}, T) <tex>\le</tex> t</tex>

Алгоритм сортировки Такая хеш-функция может быть найдена за <texdpi="130">O(n^3)</tex> целых чисел в <tex>\sqrt{n}</tex> наборов, представленный ниже, является доказательством данной леммы.

Следует отметить, что, несмотря на размер таблицы <tex dpi==Сортировка "130">O(n целых чисел ^2)</tex>, потребность в sqrtпамяти не превышает <tex dpi="130">O(n) наборов==Постановка задачи и решение некоторых проблем:</tex>, потому что хеширование используется только для уменьшения количества бит в числе.

Сложная часть алгоритма заключается в том, как поместить маленькие числа в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <texdpi="130">n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать лемму шесть. Полный размер маркера для каждого контейнера должен быть <tex>\log n/a_{1} = 3, a_{2</tex>} = 5, и маркер использует <tex>\log e</tex> битa_{3} = 7, количество маркеров <tex>g</tex> в каждом контейнере должно быть не более <tex>\log n/(2\log e)</tex>. В дальнейшем т.к. <tex>g a_{4} = \log n/(2 \log e)</tex> м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex>k \log\log n \log n</tex> блоков10, каждое м.ч. может содержать <tex>O(k \log n/g) S = O(k \log e)</tex> блоков. Заметим{1, что используем неконсервативное преимущество в <tex>\log\log n</tex> для использования леммы шесть. Поэтому предполагается4, что <tex>\log n/(2 \log e)</tex> м.ч. в каждом из которых <tex>k \log e</tex> блоков битов числа упакованный в один контейнер. Для каждого м.ч. используется маркер из <tex>\log e</tex> бит6, который показывает к какому набору он принадлежит. Предполагаем8, что маркеры так же упакованы в контейнеры как и м.ч. Так как каждый контейнер для маркеров содержит <tex>\log n/(2 \log e)</tex> маркеров9, то для каждого контейнера требуется <tex>(\log n)/2</tex> бит. Таким образом лемма шесть может быть применена для помещения м.ч. в наборы13, которым они принадлежат. Так как используется <tex>O((n \log e)/ \log n)</tex> контейнеров то время необходимое для помещения м.ч. в их наборы потребуется <tex>O((n \log e)/ 14\log n)}</tex> времени.

Рассмотрим число <tex>a</tex>После того, которое является <tex>i</tex>-ым в наборе как вышеописанный процесс повторится <texdpi="130">Sg</tex>. Рассмотрим блок <tex>a</tex> (назовем его <tex>a'</tex>)раз, который является <tex>i</tex>-ым м.ч. получится неконсервативное преимущество в <tex>S</tex>. Когда используется вышеописанный метод перемещения нескольких следующих блоков <tex>a</texdpi="150"> (назовем это <tex>a''</tex>\frac{h} {\log\log n}) в <tex>S^g</tex>раз, <tex>a''</tex> просто перемещен на позицию в наборе то время как потрачено только <texdpi="130">S</tex>, но не обязательно на позицию <tex>i</tex> O(где расположен <tex>a'</tex>gqt). Если значение блока <tex>a'</tex> одинаково для всех чисел в <tex>S</tex>времени, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex>S</tex> помещен так как каждое многократное деление происходит за линейное время <tex>a''</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем dpi="текущий блок набора130". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, помещаются последующие блоки вместе с текущим блоком в набор. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <tex>k \log e</tex> блоков это текущий блок. Таким образом после того, как помещены эти <tex>k \log e</tex> блоков в набор, удаляется изначальный текущий блок, потому, что известно, что эти <tex>k \log e</tex> блоков перемещены в правильный набор и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex>k \log eO(qt)</tex> блоках.

Стоит отметитьХеш-функция, что после нескольких уровней деления размер наборов станет маленькимкоторая используется, находится следующим образом. Леммы четыреБудут хешироватся сегменты, <tex dpi="150">\frac{\log\log n}{h}</tex>-ые, <tex dpi="150">(\frac{\log\log n}{h})^2</tex>-ые, пять и шесть расчитанны <tex dpi="130">\ldots</tex> по счету в числе. Хеш-функцию для <tex dpi="150">(\frac{\log\log n}{h})^t</tex>-ых по счету сегментов, получаем нарезанием всех <tex dpi="130">p</tex> чисел на не очень маленькие наборы. Но поскольку сортируется набор из <texdpi="150">(\frac{\log\log n}{h})^t</tex> элементов в наборы размера сегментов. Рассматривая каждый сегмент как число, получаем <texdpi="150">p(\sqrtfrac{\log\log n}{h})^t</tex> чисел. Затем получаем одну хеш-функцию для этих чисел. Так как <tex dpi="130">t < \log n</tex>, то проблем получится не должно бытьболее <tex dpi="130">\log n</tex> хеш-функций.

Algorithm Операция '''сортировки за линейное время''' (англ. ''Linear-Time-Sort(<tex>k \log\log n</tex>, <tex>level</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots</tex>, <tex>a_{t}</tex>'')

Входные данные: <texdpi="150">k 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> это неконсервативное преимуществобит, <texdpi="130">a_d_{i}.set</tex>-ые это входящие целые числа — набор, в наборе, которые надо отсортироватькотором находится <tex dpi="130">d_{i}</tex>. Следует отметить, что всего есть <texdpi="130">levelt</tex> это уровень рекурсиинаборов.

# Сортируем все <tex>if level =dpi= 1</tex> тогда изучить размер набора. Если размер меньше или равен <tex"130">\sqrtd_{ni}</tex>, то по <texdpi="130">return</tex>d_{i}. Иначе разделить этот набор в <tex>\levalue</tex> 3 набора , используя лемму три, чтобы найти медиану а затем использовать лемму 6 для сортировкиbucket sort. Для набора где Пусть все элементы равны медиане, не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого отсортированные числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. <texdpi="130">ReturnA[1..r]</tex>.# От Этот шаг занимает линейное время, так как сортируется не менее <tex>u dpi= 1</tex"150"> до <tex>k</tex>## Упаковать <tex>an^{(u)}_\frac{i2}</tex>-ый в часть из <tex>1/k</tex>-ых номеров контейнеров, где <tex>a^{(u)5}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex>1/k</tex>-ых битов <tex>a_{i}</tex> и у которого текущий блок это самый крупный блокчисел.## Вызвать Sort(Помещаем все <texdpi="130">k \log\log nA[j]</tex>, в <texdpi="130">level - 1</tex>, <tex>a^{(u)}_{0}</tex>, <tex>a^{(u)}_{1}</tex>, <tex>\ldots</tex>, <tex>a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к которому набору это число относится, уже отправлен назад к месту где число находится во входных данныхA[j]. Число имеющее наибольшее число бит в <tex>a_{i}</tex>, показывающее на ткущий блок в нем, так же отправлено назад к <tex>a_{i}set</tex>.## Отправить <tex>a_{i}-ые к их наборам, используя лемму шесть.</tex>

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

Algorithm IterateSortCall Sort(Берем <texdpi="130">k 1/e = 5</tex> для ЭП-дерева Андерссона. Следовательно, у корня будет <tex dpi="150">n^{\logfrac{1}{5}}</tex> детей, и каждое ЭП-дерево в каждом ребенке будет иметь <tex dpi="150">n^{\log 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>чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на <texdpi="130">t_{1} = n^{1/5}</tex> наборов <tex dpi="130">S_{1}, S_{2}, \log_ldots, S_{t_{k1}}((</tex>, в каждом из которых <tex dpi="150">n^{\log n)frac{4}{5}}</4)tex> чисел и <tex dpi="130">S_{i} < S_{j}, i < j</tex>. Затем, берутся <tex dpi="150">n^{\frac{8}{25}}</tex>a_чисел из <tex dpi="130">S_{0i}</tex>и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <texdpi="150">a_t_{2} = n^{\frac{1}{5}}n^{\frac{4}{25}} = n^{\frac{9}{25}}</tex>, наборов <texdpi="130">T_{1}, T_{2}, \ldots, T_{t_{2}}</tex>, аналогичных наборам <texdpi="130">a_S_{i}</tex>, в каждом из которых <tex dpi="150">n - 1^{\frac{16}{25}}</tex>);чисел. Теперь числа опускаются дальше в ЭП-дереве.

от 1 до 5# Поместить <tex>a_{i}</tex> в соответствующий набор с помощью bucket sort потомуНетрудно заметить, что наборов около <tex>\sqrt{n}перебалансирока занимает </tex># Для каждого набора <tex>S dpi= </tex"130">{<tex>a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>}, если <tex>t > sqrt{O(n}</tex>, вызвать Sort(<tex>k \log\log n)</tex>, времени с <texdpi="130">\log_{k}(O(\log n)/4)</tex>времени на уровень, <tex>a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>)аналогично стандартному ЭП-дереву Андерссона.

==Лемма №3==Выбор Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <texdpi="130">s</tex>. Имеется <tex dpi="150">t = n^{1 -ого наибольшего числа среди (\frac{4}{5})^S}</tex> наборов по <texdpi="150">n^{(\frac{4}{5})^S}</tex> чисел упакованных в каждом. Так как каждый узел на данном уровне имеет <texdpi="150">p = n^{\frac{1}{5} \cdot (\frac{4}{5})^S}</gtex> детей, то на <tex dpi="130">s + 1</tex> контейнеров может быть сделана за уровень опускаются <texdpi="150">Oq = n^{\frac{2}{5} \cdot (n \log g/gfrac{4}{5})^S}</tex> время и с использованием чисел для каждого набора, или всего <texdpi="150">O(qt \geqslant n/g)^{\frac{2}{5}}</tex> места. Конкретно медиана может быть так найденачисел для всех наборов за один раз.

==Лемма №4==Если Так как <texdpi="130">gq</tex> целых чисел, в сумме использующие не надо полностью сортировать и <texdpi="130">(\log n)/q = p^2</tex> бит, упакованы в один контейнер, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы за время <tex>O((n/g) \log g)</tex>то можно использовать [[#lemma6|лемму №6]] для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с использованием <tex>Oпомощью [[Сортировка Хана#Signature sorting|signature sorting]]. Для этого используется линейная техника многократного деления (n/gангл. ''multi-dividing technique'')</tex> места.

Для контейнеров вне групп (которых Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя [[#lemma6|лемму №6]], делается разделение. Так как получено неконсервативное преимущество в <texdpi="150">(\sqrtfrac{h}{\log\log n}()^g - 1)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется работа происходит на уровнях не более ниже, чем <texdpi="130">O(2 \log\log\log n/g)</tex> места и времени. После всего этого используем bucket sorting вновь для сортировки , то алгоритм занимает <texdpi="150">O(\frac{qt \log\log n}{g(\log h - \log\log\log n) - \log\log\log n}) = O(\log\log n)</tex> контейнеров. таким образом все числа отсортированывремени.

Заметим, что когда В итоге разделились <texdpi="130">g = O( \log n)q</tex> сортировка чисел <texdpi="130">O(n)p</tex> чисел числами в каждый набор. То есть получилось, что <texdpi="130">n/gS_{0} < e_{1} </tex> контейнеров произойдет за время S_{1} <tex>O((n/g) \log\log n)ldots </tex>, с использованием O(n/g) места. Выгода очевидна.==Лемма №5==Если принять, что каждый контейнер содержит e_{p} <tex> \log m > \log nS_{p}</tex> бит, и где <texdpi="130">ge_{i}</tex> чисел, в каждом из которых {{---}} сегмент <texdpi="130">(\log m)/ga_{i}</tex> бит, упакованы полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в один контейнерподзадачах. Если каждое число имеет маркерПредполагаем, содержащий <tex>(\log n)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы что числа хранятся в один контейнер таким же образоммассиве <texdpi="130">^*B</tex>так, что и числа, тогда в <texdpi="130">nS_{i}</tex> чисел предшествуют числам в <texdpi="130">n/gS_{j}</tex> контейнерах могут быть отсортированы по их маркерам за время если <texdpi="130">O((n \log\log n)/g)</tex> с использованием i <tex>O(n/g)j</tex> места.(*): если число и <texdpi="130">ae_{i}</tex> упаковано как хранится после <texdpi="130">s</tex>S_{i -ое число в <tex>t1}</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в но до <texdpi="130">tS_{i}</tex>-ом контейнере для маркеров.

Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>( \log n)/2</tex> бит. Сортировка сгруппирует контейнеры для чисел как в четвертой лемме. Перемещаем каждую группу контейнеров для чисел. ==Лемма №6==предположим, что каждый контейнер содержит <tex>\log m \log\log n > \log n</tex> бит, что <tex>g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>(\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>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g \le \log n</tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)</tex>==См.также==* [[Сортировка подсчетом]]* [[Цифровая сортировка]]

==ЛитераураИсточники информации==# * [http://www.sciencedirect.com/science/article/pii/S019667740300155X Deterministic Sorting in O(n \log\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://dl.acm.org/citation.cfm?id=1236460 A. Andersson, M. Thorup. Dynamic ordered sets with exponential search trees.]* [[wikipedia:en:Integer_sorting|Wikipedia {{---}} Integer sorting]]

[[Категория: СортировкиСортировка]]