25
правок
Изменения
Нет описания правки
'''Сортировка Хана ''' (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> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.
{{Определение
}}
==Определения== {{ Определение | definition = '''Контейнер''' {{---}} объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.}}{{ Определение | definition = Алгоритм: Пусть целое число , сортирующий <texdpi="130">b >= 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} = k \{h_{a} \mid 0 log (m + n)< a /tex> с < 2^b, a tex dpi="130">k \equiv geqslant 1 (\mod 2)\}</tex> и для всех , тогда сортировка происходит с '''неконсервативным преимуществом''' <tex dpi="130">k</tex>.}}{{ Определение | definition = Для множества <texdpi="130">xS</tex> из определим <texdpi="130">U: h_{a}\min(xS) = (ax \mod 2^b) div 2^min\limits_{b - sa \in S}a</tex>.
}}
{{Лемма|id =lemma2|about =Signature sorting№ 2|statement =Выбор <tex dpi="130">s</tex>-ого наибольшего числа среди <tex dpi="130">n</tex> чисел, упакованных в <tex dpi="150">\frac{n}{g}</tex> контейнеров, может быть сделан за время <tex dpi="150">O(\frac{n \log g}{g})</tex> и с использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти. В данной сортировке используется следующий алгоритм:том числе, так может быть найдена медиана.
|proof = Так как используется только <texdpi="150">a_\frac{\log n}{12}</tex> бит в каждом контейнере для хранения <tex dpi= 3"130">g</tex> чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает <texdpi="150">a_O(\frac{n}{g})</tex> времени и памяти. Так как используется <tex dpi="150">\frac{\log n}{2}</tex> = 5бит на контейнер, понадобится <texdpi="130">a_\sqrt{3n}</tex> = 7, шаблонов для всех контейнеров. Затем поместим <texdpi="150">a_g < \frac{4\log n}{2}</tex> контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более <tex dpi= 10"130">g - 1</tex> контейнеров, S которые не смогут образовать группу. Поэтому не более <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>-целых векторов, 4где <tex dpi="130">i</tex>-ый вектор содержит <tex dpi="130">i</tex>-ое число из входящего вектора. Эта транспозиция может быть сделана за время <tex dpi="130">O(g \log g)</tex>, 6с использованием <tex dpi="130">O(g)</tex> памяти. Для всех групп это занимает время <tex dpi="150">O(\frac{n \log g}{g})</tex>, 8, 9, 13, 14с использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти.
}}
{{Лемма
|id=lemma3. lemma4|about = № 4|statement=Выбор Примем, что каждый контейнер содержит <texdpi="130"> \log m >s\log n</tex>-ого наибольшего числа среди бит, и <texdpi="130">ng</tex> чисел упакованных , в каждом из которых <texdpi="150">n/\frac{\log m}{g}</tex> контейнеров может быть сделана за бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <texdpi="150">O(nlogg/g)\frac{\log n}{2g}</tex> время бит, и с использованием <texdpi="130">O(n/g)</tex> места. Конкретно медиана может быть так найдена.|proof=Так как мы можем делать попарное сравнение маркеров упакованы в один контейнер таким же образом<texdpi="130">g^*</tex> чисел в одном контейнере с , что и числа, тогда <texdpi="130">gn</tex> числами чисел в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, мы можем упаковать медианы из первого, второго, ..., <texdpi="150">\frac{n}{g}</tex>-ого чисел из 5 контейнеров в один контейнер контейнерах могут быть отсортированы по их маркерам за константное время. Таким образом набор <texdpi="150">SO(\frac{n \log\log n}{g})</tex> из медиан теперь содержится в с использованием <texdpi="150">O(\frac{n/(5g}{g})</tex> контейнерахпамяти. Рекурсивно находим медиану (*): если число <texdpi="130">ma</tex> в упаковано как <texdpi="130">Ss</tex>. Используя -ое число в <texdpi="130">mt</tex> уберем хотя бы -ом контейнере для чисел, тогда маркер для <texdpi="130">n/4a</tex> чисел среди упакован как <texdpi="130">ns</tex>. Затем упакуем оставшиеся из -ый маркер в <texdpi="130">n/gt</tex> контейнеров в -ом контейнере для маркеров. |proof = Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <texdpi="150">3n/4g\frac{\log n}{2}</tex> бит. Сортировка сгруппирует контейнеры для чисел как в [[#lemma3|лемме №3]]. Перемещаем каждую группу контейнеров и затем продолжим рекурсиюдля чисел.
}}
{{Лемма
|id=lemma4.lemma5|about = № 5|statement=Если <tex>g</tex> целых чиселПредположим, в сумме использующие <tex>(logn)/2</tex> бит, упакованы в один что каждый контейнер, тогда содержит <texdpi="130">\log m \log\log n</tex> чисел в <tex>\log n/g</tex> контейнерах могут быть отсортированы за время бит, что <texdpi="130">O((n/g)logg)</tex>чисел, с использованием <tex>O(n/g)</tex> места.|proof=Так как используется только <tex>(logn)/2</tex> бит в каждом контейнере для хранения из которых <texdpi="150">\frac{\log m}{g}</tex> чиселбит, мы можем использовать bucket sorting чтобы отсортировать все контейнеры. представляя каждый как числоупакованы в один контейнер, что занимает <tex>O(n/g)</tex> времени и места. Потомукаждое число имеет маркер, что мы используем <tex>(logn)/2</tex> бит на контейнер нам понадобится содержащий <texdpi="150">\sqrt frac{\log n}{2g}</tex> шаблонов для всех контейнеров. Затем поместим бит, и что <texdpi="130">g < (logn)/2</tex> контейнеров с одинаковым шаблоном маркеров упакованы в одну группуодин контейнер тем же образом что и числа. Для каждого шаблона останется не более Тогда <texdpi="130">g - 1n</tex> контейнеров которые не смогут образовать группу. Поэтому не более чисел в <texdpi="150">\sqrtfrac{n}(g - 1)</tex> контейнеров не смогут сформировать группу. Для каждой группы мы помещаем <tex>i</tex>-е число во всех <tex>{g}</tex> контейнерах в один. Таким образом мы берем <tex>g</tex> <tex>g</tex>-целых векторов и получаем <tex>g</tex> <tex>g</tex>-целых векторов где <tex>i</tex>-ый вектор содержит <tex>i</tex>-ое число из входящего вектора. Эта транспозиция может могут быть сделана отсортированы по своим маркерам за время <texdpi="150">O(glogg)</tex>, с использованием <tex>O(g)</tex> места. Для всех групп это занимает время <tex>O((\frac{n/}{g)logg})</tex>, с использованием <texdpi="150">O(\frac{n/}{g})</tex> местапамяти.
|proof = Заметим, что несмотря на то, что длина контейнера <tex dpi="130">\log m \log\log n</tex> бит, всего <tex dpi="130">\log m</tex> бит используется для хранения упакованных чисел. Так же как в [[#lemma3|лемме №3]] и [[#lemma4|лемме №4]] сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем <tex dpi="130">g \log\log n</tex> вместо <tex dpi="130">g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей <tex dpi="130">g \log\log n</tex> контейнеров, упаковываем <tex dpi="130">g \log\log n</tex> контейнеров вне групп (которых в <tex dpi="130">g</tex>, упаковывая <texdpi="130">\sqrt(log\log n)</tex> контейнеров в один. Далее делаем транспозицию над <tex dpi="130">g</tex> контейнерами. Таким образом перемещение занимает всего <tex dpi="130">O(g - 1\log\log n)</tex> штук) мы просто разберем времени для каждой группы и соберем заново контейнеры. На это потребуется не более <texdpi="150">O(\frac{n/}{g})</tex> места и временидля всех чисел. После всего этого мы используем bucket sorting вновь для сортировки завершения транспозиции, распаковываем <tex dpi="130">g</tex> контейнеров в <texdpi="130">g \log\log n</tex> контейнеров. таким образом мы отсортируем все числа.}}
}}
{{Лемма
|id=lemma6.|about = № 6|statement=предположим, что каждый контейнер содержит <texdpi="130">logmloglogn > logn</tex> бит, что <tex>gn</tex> целых чисел, можно отсортировать в каждом из которых <texdpi="130">(logm)/g\sqrt{n}</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий наборов <texdpi="130">(logn)/(2g)S_{1}</tex> бит, и что <texdpi="130">gS_{2}</tex> маркеров упакованы в один контейнер тем же образом что и числа, тогда <texdpi="130">n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(n/g)\ldots</tex>, с использованием <texdpi="130">O(S_{\sqrt{n/g)}}</tex> памяти.|proof=Заметимтаким образом, что несмотря на то, что длина контейнера в каждом наборе <texdpi="130">logmloglogn</tex> бит всего <tex>logm\sqrt{n}</tex> бит используется для хранения упакованных чисел. Так же как в леммах четыре и пять мы сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел мы помещаем <texdpi="130">gloglognS_{i} </tex> вместо <tex>gS_{j}</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе содержащей при <texdpi="130">gloglogn</tex> контейнеров мы сначала упаковываем i <tex>gloglognj</tex> контейнеров в <tex>g</tex> контейнеров упаковывая <tex>loglogn</tex> контейнеров в один. Далее мы делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего , за время <texdpi="150">O(gloglogn\frac{n \log\log n} {\log k})</tex> времени для каждой группы и место <texdpi="130">O(n/g)</tex> времени для всех чисел. После завершения транспозиции, мы далее распаковываем с неконсервативным преимуществом <texdpi="130">gk \log\log n</tex> контейнеров в <tex>gloglogn</tex> контейнеров.}}
Постановка задачи и решение некоторых проблем:
Стоит отметить, что после нескольких уровней деления размер наборов станет маленькимпроцесс помещения нестабилен, т. Леммы четыре, пять и шесть расчитанны к. основан на не очень маленькие наборы. Но поскольку мы сортируем набор алгоритме из <tex>n</tex> элементов в наборы размера <tex>\sqrt{n}</tex>, то проблем не должно быть[[#lemma5|леммы №5]].
Рассмотрим число <texdpi="130">kloglogna</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>, но не обязательно на позицию <texdpi="130">a_{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>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном набореработают на общем блоке, который назовем "текущий блок набора". Блоки, которые надо отсортироватьпредшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, последующие блоки помещаются в набор вместе с текущим блоком. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <texdpi="130">levelk \log e</tex> блоков {{---}} это уровень рекурсиитекущий блок. Таким образом, после того, как эти <tex dpi="130">k \log e</tex> блоков помещены в набор, изначальный текущий блок удаляется, потому что известно, что эти <tex dpi="130">k \log e</tex> блоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex dpi="130">k \log e</tex> блоках.
Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы [[#lemma3|3]], [[#lemma4|4]], [[#lemma5|5]] расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <texdpi="130">if level == 1n</tex> тогда изучить размер набора. Если размер меньше или равен элементов в наборы размера <texdpi="130">\sqrt{n}</tex>, то <tex>return</tex>. Иначе разделить этот набор в <= 3 набора используя лемму три, чтобы найти медиану а затем использовать лемму 6 для сортировки. Для набора где все элементы равны медиане, проблем быть не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. <tex>Return</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). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.3# От <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="150">\frac{1}{k}</tex>-ых битов <texdpi="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>. end## Отправляем <tex dpi="130">a_{i}</tex>-ые к их наборам, используя [[#lemma5|лемму №5]].
Algorithm IterateSort
Call Sort(<tex>kloglognSort(advantage</tex>, <texdpi="130">\log_{k}((logn\log n)/4)</tex>, <texdpi="130">a_{0}</tex>, <texdpi="130">a_{1}</tex>, ...<tex dpi="130">\ldots</tex>, <texdpi="130">a_{n - 1}</tex>);
от 1 до 5
# Помещаем <tex dpi="130">a_{i}</tex> в соответствующий набор с помощью блочной сортировки (англ. ''bucket sort''), потому что наборов около <tex dpi="130">\sqrt{n}</tex>.
# Для каждого набора <tex dpi="130">S = </tex>{<tex dpi="130">a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>}, если <tex dpi="130">t > \sqrt{n}</tex>, вызываем <tex>Sort(advantage</tex>, <tex dpi="130">\log_{k}(\frac{\log n}{4})</tex>, <tex dpi="130">a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>).
Время работы алгоритма <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|лемме №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="130">2^{b - s}</tex>).
Такая хеш-функция может быть найдена за <tex dpi="130">O(n^3)</tex>.
Следует отметить, что, несмотря на размер таблицы <tex dpi="130">O(n^2)</tex>, потребность в памяти не превышает <tex dpi="130">O(n)</tex>, потому что хеширование используется только для уменьшения количества бит в числе.
==Сортировка по ключу==
Предположим, что <tex dpi="130">n</tex> чисел должны быть отсортированы, и в каждом <tex dpi="130">\log m</tex> бит. Будем считать, что в каждом числе есть <tex dpi="130">h</tex> сегментов, в каждом из которых <tex dpi="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>. Так как используется '''сортировка по ключу''' (англ. ''signature sorting'') то перед тем, как делать вышеописанное разделение, необходимо поделить биты в <tex dpi="130">a_{i}</tex> на <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>. (<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>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах (<tex dpi="130">a_{i}</tex>-ом и <tex dpi="130">b_{i}</tex>-ом) хешируются, и получается <tex dpi="150">\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> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <tex dpi="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'') в <tex dpi="150">\frac{h} {\log\log n}</tex>.
После того, как вышеописанный процесс повторится <tex dpi="130">g</tex> раз, получится неконсервативное преимущество в <tex dpi="150">(\frac{h} {\log\log n})^g</tex> раз, в то время как потрачено только <tex dpi="130">O(gqt)</tex> времени, так как каждое многократное деление происходит за линейное время <tex dpi="130">O(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> чисел на <tex dpi="150">(\frac{\log\log n}{h})^t</tex> сегментов. Рассматривая каждый сегмент как число, получаем <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'')
Входные данные: <tex dpi="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">A[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) времени и памяти==
Для сортировки <tex dpi="130">n</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> для ЭП-дерева Андерссона. Следовательно, у корня будет <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>. Затем, берутся <tex dpi="150">n^{\frac{8}{25}}</tex> чисел из <tex dpi="130">S_{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>, в каждом из которых <tex dpi="150">n^{\frac{16}{25}}</tex> чисел. Теперь числа опускаются дальше в ЭП-дереве.
Нетрудно заметить, что перебалансирока занимает <tex dpi="130">O(n \log\log n)</tex> времени с <tex dpi="130">O(n)</tex> времени на уровень, аналогично стандартному ЭП-дереву Андерссона.
Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <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> чисел в каждом. Так как каждый узел на данном уровне имеет <tex dpi="150">p = n^{\frac{1}{5} \cdot (\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>.
==Собственно сортировка с использованием O(nloglogn) времени и памятиСм. также==Для сортировки <tex>n</tex> целых чисел в диапазоне от {<tex>0, 1, ..., m - 1</tex>} мы предполагаем, что используем контейнер длины <tex>O(log(m + n))</tex> в нашем консервативном алгоритме. Мы всегда считаем что все числа упакованы в контейнеры одинаковой длины. * [[Сортировка подсчетом]]* [[Цифровая сортировка]]