Изменения

'''Сортировка Хана ''' (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это дерево поиска, в котором все ключи хранятся в листьях этого дерева и т.д.}}{{Определение|id=def2. |definition=Алгоритм сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> называется консервативным, если длина контейнера (число бит в контейнере), является <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм неконсервативный.}}{{Определение|id=def3. |definition=Если мы сортируем целые числа из множества {0, 1, ..., <tex>m</tex> - 1} с длиной контейнера <tex>klog(m + n)</tex> с <tex>k</tex> >= 1, тогда мы сортируем с неконсервативным преимуществом <tex>k</tex>количество детей у каждого узла уменьшается экспоненциально от глубины узла.}}{{Определение|id=def4. |definition=Для множества <tex>S</tex> определимmin(<tex>S</tex>) = min(<tex>a</tex>:<tex>a</tex> принадлежит <tex>S</tex>)max(<tex>S</tex>) = max(<tex>a</tex>:<tex>a</tex> принадлежит <tex>S</tex>)Набор <tex>S1</tex> < <tex>S2</tex> если max(<tex>S1</tex>) <= min(<tex>S2</tex>)

==Уменьшение числа бит в числах==Один из способов ускорить сортировку {{-[[Файл:Exp--}} уменьшить число бит в числеtree. Один из способов уменьшить число бит в числе {{png|400px|thumb|right|Общая структура ЭП-дерева]] Структура ЭП--}} использовать деление пополам (эту идею впервые подал van Emde Boasдерева: 1). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий Корень имеет <texdpi="130">O\Theta (mn^e)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до сыновей <texdpi="130">O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования 0 <tex>ne </tex> чисел в таблицу размера <tex>O(n^21 )</tex> за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и RamanВсе сыновья являются ЭП-деревьями.

Алгоритм: Пусть целое число 2) Каждое поддерево корня имеет <tex>b >dpi= 0</tex"130"> и пусть <tex>U = \Theta(n^{0, \ldots, 2^b - 1\}</tex>. Класс <tex>H_{b,s}</tex> хэш функций из <tex>U</tex> в <tex>\{0, \ldots, 2^s - 1\}</tex> определен как <tex>H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\mod 2)\}</tex> и для всех <tex>x</tex> из <tex>U: h_{ae}(x) = (ax \mod 2^b) div 2^{b - s}</tex>сыновей.

Номер один.==Определения== {{ЛеммаОпределение |iddefinition =lemma1 '''Контейнер''' {{---}} объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.}}{{ Определение |statementdefinition =Даны целые числа Алгоритм, сортирующий <texdpi="130">bn</tex> >= целых чисел из множества <tex>s</tex> >dpi= 0 и <tex"130">T</tex> является подмножеством \{0, ...1, \ldots, <tex>2^b</tex> m - 1\}, содержащим <tex>n</tex> элементов, и называется '''консервативным''', если длина контейнера (число бит в контейнере) равна <texdpi="130">tO(\log(m + n))</tex> >. Если длина больше, то алгоритм '''неконсервативный'''. }}{{ Определение | definition = Если сортируются целые числа из множества <texdpi="130">2^\{0, 1, \ldots, m -s + 1\}</tex>Сс длиной контейнера <texdpi="130">^k_{k \log (m + n})</tex>. Функция с <texdpi="130">h_{a}k \geqslant 1</tex> принадлежащая <tex>H_{b,s}тогда сортировка происходит с '''неконсервативным преимуществом''' </tex> может быть выбрана за время <tex>O(bn^2)</texdpi="130"> так, что количество коллизий <tex>coll(h_{a}, T) <= tk</tex>.

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

Такая хэш функция может быть найдена за Набор <texdpi="130">OS1 < S2</tex> если <tex dpi="130">\max(S1) \leqslant \min(n^3S2)</tex>.}}

Следует отметить{{ Определение | definition = Предположим, что несмотря на размер таблицы есть набор <texdpi="130">O(n^T</tex> из <tex dpi="130">p</tex> чисел, которые уже отсортированы как <tex dpi="130">a_{1}, a_{2)}, \ldots, a_{p}</tex> и набор <tex dpi="130">S</tex> из <tex dpi="130">q</tex>чисел <tex dpi="130">b_{1}, b_{2}, потребность в памяти не превышает \ldots, b_{q}</tex>O(n). Тогда '''разделением''' <tex dpi="130">q</tex> чисел <tex dpi="130">p</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} < S_{1} < \ldots < a_{p} < S_{p}</tex>.}}

==Signature sortingЛеммы==В данной сортировке используется следующий алгоритм:

Предположим, что {{Лемма|id = lemma1|about = № 1|statement = Даны целые числа <texdpi="130">nb \geqslant s \geqslant 0</tex> чисел должны быть сортированы, и в каждом <texdpi="130">logmT</tex> бит. Мы рассматриваем, что в каждом числе есть является подмножеством множества <texdpi="130">h\{0, \ldots, 2^b - 1\}</tex> сегментов, в каждом из которых содержащим <texdpi="130">log(m/h)n</tex> бит. Теперь мы применяем хэширование ко всем сегментам элементов, и получаем <texdpi="130">2hlognt \geqslant 2^{-s + 1}С^k_{n}</tex> бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке Функция <texdpi="130">nh_{a}</tex> чисел по , принадлежащая <texdpi="130">mH_{b,s}</tex> бит в каждом стала задачей по сортировке , может быть выбрана за время <texdpi="130">nO(bn^2)</tex> чисел по так, что количество коллизий <texdpi="130">logcoll(m/hh_{a}, T)\leqslant t</tex> бит в каждом.}}

Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{Лемма|id = lemma2|about = № 2}|statement = Выбор </texdpi="130">, ..., <tex>a_{p}s</tex> {{---}} ого наибольшего числа среди <texdpi="130">pn</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 \log g}</tex> < {<tex>a_{2g})</tex>} < ... < {и с использованием <texdpi="150">a_O(\frac{p}</tex>n} < <tex>S_{pg})</tex>памяти. Т.к. мы используем signature sortingВ том числе, до того как делать вышеописанное разделение, мы поделим биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов и возьмем некоторые из них. Мы так же поделим биты для каждого числа из <tex>S</tex> и оставим только один в каждом числе. По существу для каждого <tex>a_{i}</tex> мы возьмем все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегменты, которые мы берем для числа в <tex>S</tex>, {{---}} сегмент, который выделяется из <tex>a_{i}</tex>. Таким образом мы преобразуем начальную задачу о разделении <tex>n</tex> чисел в <tex>logm</tex> бит в несколько задач на разделение с числами в <tex>log(m/h)</tex> бит может быть найдена медиана.

{{Лемма|id = lemma3|about = № 3|statement = Если <texdpi="130">a_{1}g</tex> = 3целых чисел, в сумме использующих <texdpi="150">a_\frac{\log n}{2}</tex> бит, упакованы в один контейнер, тогда <tex dpi= 5, "130">n</tex> чисел в <texdpi="150">a_\frac{n}{3g}</tex> = 7, контейнерах могут быть отсортированы за время <texdpi="150">a_O(\frac{4n \log g}{g})</tex> с использованием <tex dpi= 10, S = "150">O(\frac{n}{1, 4, 6, 8, 9, 13, 14g})</tex> памяти.

|proof =Так как используется только <tex dpi="150">\frac{\log n}{2}</tex> бит в каждом контейнере для хранения <tex dpi="130">g</tex> чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает <tex dpi="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> памяти. Для всех групп это занимает время <tex dpi="150">O(\frac{n \log g}{g})</tex>, ниже представлены несколько полезных леммс использованием <tex dpi="150">O(\frac{n}{g})</tex> памяти.

Номер два.{{Лемма|id=lemma2. |statement=Для контейнеров вне групп (которых <texdpi="130">\sqrt{n}(g - 1)</tex> целых чисел можно отсортировать в штук) разбираем и собираем заново контейнеры. На это потребуется не более <texdpi="150">O(\sqrtfrac{n}</tex> наборов <tex>S_{1g})</tex>, времени и памяти. После всего этого используем карманную сортировку вновь для сортировки <texdpi="130">S_{2}n</tex>контейнеров. Таким образом, все числа отсортированы...  Заметим, что когда <texdpi="130">S_{g = O( \sqrt{log n}})</tex> таким образом, что в каждом наборе сортировка <texdpi="130">\sqrt{O(n})</tex> чисел и в <texdpi="150">S_\frac{in}</tex> < <tex>S_{jg}</tex> при <tex>i</tex> < <tex>j</tex>, контейнеров произойдет за время <texdpi="150">O(nloglogn/logk(\frac{n}{g})</tex> и место <texdpi="130">O(\log\log n)</tex> с не консервативным преимуществом использованием <texdpi="150">kloglognO(\frac{n}{g})</tex>|proof=Доказательство данной леммы будет приведено далее в тексте статьипамяти. Выгода очевидна.

|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=lemma5.|statement=Если принятьЗаметим, что каждый контейнер содержит если длина контейнера <texdpi="130">logm > logn\log m \log\log n</tex> бит, и только <texdpi="130">g</tex> чисел, в каждом из которых <tex>(logm)/g\log m</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(logn)/(2g)</tex> бит, и используется для упаковки <texdpi="130">g\leqslant \log n</tex> маркеров упакованы чисел в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел выбор в <tex>n/g</tex> контейнерах могут [[#lemma2|лемме №2]] может быть отсортированы по их маркерам сделан за время и память <texdpi="150">O((nloglogn)/g)</tex> с использованием <tex>O(\frac{n/}{g})</tex> места.(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер потому что упаковка в <tex>t</tex>-ом контейнере для маркеров.доказательстве [[#lemma2|proof=Контейнеры для маркеров могут лемме №2]] теперь может быть отсортированы с помощью bucket sort потому, что каждый контейнер использует сделана за время <texdpi="150">O(logn\frac{n}{g})/2</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> контейнеров.}}

Заметим, что если длина контейнера |proof = Алгоритм сортировки <texdpi="130">logmloglogn</tex> и только <tex>logm</tex> бит используется для упаковки <tex>g <= lognn</tex> целых чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <texdpi="130">O(\sqrt{n/g)}</tex>наборов, потомупредставленный ниже, что упаковка в доказатльстве является доказательством данной леммы три теперь может быть сделана за время <tex>O(n/g)</tex>.

Сложная часть алгоритма заключается в том, как поместить маленькие числа в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что Рассмотрим проблему сортировки <texdpi="130">n</tex> целых чисел уже поделены в из множества <texdpi="130">e\{0, 1, \ldots, m - 1\}</tex> наборов. Мы можем использовать в <texdpi="130">loge\sqrt{n}</tex> битов чтобы сделать марки для каждого наборанаборов, как в условии леммы. Теперь хотелось бы использовать лемму шесть. Полный размер маркера для каждого контейнера должен быть <tex>logn/2</tex>Предполагаем, и маркер использует что каждый контейнер содержит <texdpi="130">logek \log\log n \log m</tex> бит, количество маркеров <tex>g</tex> и хранит число в каждом контейнере должно быть не более <texdpi="130">logn/(2loge)\log m</tex>бит. В дальнейшем т.к. Поэтому неконсервативное преимущество {{---}} <texdpi="130">g = logn/(2loge)k \log \log n</tex> м.ч. должны влезать в контейнер. Каждый контейнер содержит Также предполагаем, что <texdpi="130">kloglognlogn\log m \geqslant \log n \log\log n</tex> блоков, каждое м.ч. может содержать Иначе можно использовать radix sort для сортировки за время <texdpi="130">O(klogn/g) = O(klogen \log\log n)</tex> блокови линейную память. Заметим, что мы используем неконсервативное преимущество в Делим <texdpi="130">loglogn\log m</tex> бит, используемых для использования леммы шесть. Поэтому мы предполагаем что <tex>logn/(2loge)</tex> м.ч. представления каждого числа, в каждом из которых <texdpi="130">kloge\log n</tex> блоков битов числа упакованный в один контейнер. Для каждого м.ч. мы используем маркер из Таким образом, каждый блок содержит как минимум <texdpi="130">loge\log\log n</tex> бит, который показывает к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры как и м.ч. Так как каждый контейнер для маркеров содержит <texdpi="130">logn/(2loge)i</tex> маркеров, то для каждого контейнера требуется -ый блок содержит с <texdpi="150">(logn)/2\frac{i \log m} {\log n}</tex> бит. Таким образом лемма шесть может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется -ого по <texdpi="150">O(\frac{(nlogei + 1)/logn\log m} {\log n - 1})</tex> контейнеров то время необходимое для помещения м-ый биты.чБиты считаются с наименьшего бита, начиная с нуля. в их наборы потребуется Теперь у нас имеется <texdpi="130">O((nloge)/logn)2 \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> м.ч. могут быть разделены на не более чем три группы: <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>. Тогда убираем из дальнейшего рассмотрения <tex dpi="150">\frac{\log m}{\log n}</tex> бит (наибольший блок) из каждого числа, принадлежащего <tex dpi="130">S'_{2}</tex>. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex dpi="130">\log n</tex> блоков, для каждого числа потребуется не более <tex dpi="130">\log n</tex> стадий, чтобы поместить его в набор половинного размера. За <tex dpi="130">2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <tex dpi="150">\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> блоков, каждое м.ч. может содержать <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]] может быть применена для помещения м.ч. в наборы размера , которым они принадлежат. Так как используется <texdpi="150">O(\sqrtfrac{n\log e}{ \log n})</tex>контейнеров, то проблем не должно бытьвремя, необходимое для помещения м.ч. в их наборы, равно <tex dpi="150">O(\frac{n \log e}{ \log n})</tex>.

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

1Рассмотрим число <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> блоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex dpi="130">k \log e</tex> блоках.

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

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

end# Если <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="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]].

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>);

Для каждого набора Спуск вниз можно рассматривать как сортировку <tex dpi="130">q</tex>S чисел в каждом наборе вместе с <tex dpi= "130">p</tex>{числами <texdpi="130">a_{i_{0}1}, a_{i_{1}2}, ...\ldots, a_{i_{t}p}</tex>}из ЭП-дерева, так, если что эти <texdpi="130">t > sqrt{n}q</tex>, вызвать Sort(чисел разделены в <texdpi="130">kloglognp + 1</tex>, наборов <texdpi="130">log_S_{0}, S_{1}, \ldots, S_{kp}((logn)/4)</tex>таких, что <texdpi="130">a_{i_S_{0}}, < a_{i_{1}}, ..., < \ldots < a_{i_p} < S_{t}p}</tex>).

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

Берем После <tex>1/e dpi= 5</tex> для экспоненциального поискового дереве Андерссона. Поэтому у корня будет <tex"130">n^{1/5}g</tex> детей и каждое Э.П.дерево сокращений бит в [[Сортировка Хана#Signature sorting|signature sorting]] получаем неконсервативное преимущество в каждом ребенке будет иметь <texdpi="150">n^(\frac{4/5h}</tex> листьев. В отличии от оригинального дерева, мы будем вставлять не один элемент за раз а <tex>d^2</tex>, где <tex>d</tex> {{---\log\log n}} количество детей узла дерева, где числа должны спуститься вниз.Но мы не будем сразу опускать донизу все <tex>d)^2g</tex> чисел. Мы будем полностью опускать все <tex>d^2</tex> чисел на один уровень. В корне мы опустим <tex>n^{2/5}</tex> чисел на следующий уровень. После тогоне волнуемся об этих сокращениях до конца потому, как что после получения неконсервативного преимущества мы опустили все числа на следующий уровень мы успешно разделили числа можем переключиться на [[#lemma6|лемму №6]] для завершения разделения <tex>t_{1} dpi= n^{1/5}</tex> наборов <tex>S_{1}, S_{2}, ..., S_{t_{1}}</tex>, в каждом из которых <tex"130">n^{4/5}q</tex> чисел и с помощью <texdpi="130">S_{i} < S_{j}, i < j</tex>. Затем мы берем <tex>n^{(4/5)(2/5)}p</tex> чисел из <tex>S_{i}</tex> за раз и опускаем их на следующий уровень Э.П.дереванаборы. Повторяем этоЗаметим, пока все числа не опустятся на следующий уровень. На этом шаге мы разделили числа на что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex>t_{2} = n^{1/5}n^{4/25} dpi= n^{9/25}</tex"130"> наборов <tex>T_{1}, T_{2}, ..., T_{t_{2}}w</tex> в каждом из которых подзадач разделения на <texdpi="130">n^{16/25}w</tex> чисел, аналогичным наборам поднаборов для какого-то числа <texdpi="130">S_{i}w</tex>. Теперь мы можем дальше опустить числа в нашем Э.П.дереве.

Нам следует нумеровать уровни ЭТеперь для каждого набора все его поднаборы в подзадачах собираются в один набор.П.дерева с корняЗатем, используя [[#lemma6|лемму №6]], начиная с нуляделается разделение. Рассмотрим спуск вниз на уровне Так как получено неконсервативное преимущество в <texdpi="150">s</tex>. Мы имеем <tex>t = n^(\frac{1 - (4/5)^sh}</tex> наборов по <tex>{\log\log n^{(4/5})^s}g</tex> чисел в каждом. Так как каждый узел и работа происходит на данном уровне имеет уровнях не ниже, чем <texdpi="130">p = 2 \log\log\log n^{(1/5)(4/5)^s}</tex> детей, то на алгоритм занимает <texdpi="150">s + 1</tex> уровень мы опустим <tex>q = O(\frac{qt \log\log n^}{g(2/5\log h - \log\log\log n)(4/5- \log\log\log n})^s}</tex> чисел для каждого набора или всего <tex>qt >= O(\log\log n^{2/5})</tex> чисел для всех наборов за один развремени.

Так как нам не надо полностью сортировать В итоге разделились <texdpi="130">q</tex> чисел и <texdpi="130">q p</tex> числами в каждый набор. То есть получилось, что <tex dpi= "130">S_{0} < e_{1} < S_{1} < \ldots < e_{p^2} < S_{p}</tex>, где <tex dpi="130">e_{i}</tex> {{---}} сегмент <tex dpi="130">a_{i}</tex>, есть возможность использовать лемму 2 для сортировкиполученный с помощью битового сокращения. Для этого нам надо неконсервативное преимущество которое мы получим нижеТакое разделение получилось комбинированием всех поднаборов в подзадачах. Для этого используем линейную технику многократного деления (multiПредполагаем, что числа хранятся в массиве <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 -dividing technique) чтобы добиться этого1}</tex>, но до <tex dpi="130">S_{i}</tex>.

После того, как мы повторили вышеописанный процесс Пусть <texdpi="130">gB[i]</tex> раз мы получили неконсервативное преимущество находится в поднаборе <texdpi="130">(h/loglogn)^gB[i].subset</tex> раз. Чтобы позволить разделению выполниться, в то время как мы потратили только для каждого поднабора помещаем все <texdpi="130">O(gqt)B[j]</tex> времени, так как каждое многократное деление делятся за линейное время в <texdpi="130">O(qt)B[j].subset</tex>.

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

Procedure linearТеперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <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> в ЭП-Timeдереве. Полное число хешированных бит в контейнере равно <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>-Sortые — хешированные биты, а нули {{---}} это просто нули. Сначала упаковываем <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> контейнеров. Считаем, что время, потраченное на один контейнер — константа.

Входные данные: <tex>r > = n^{2/5}</tex> чисел <tex>d_{i}</tex>, <tex>d_{i}</tex>.value значение числа <tex>d_{i}</tex> в котором <tex>(2logn)/(cloglogn)</tex> бит, <tex>d_{i}.set</tex> набор, в котором находится <tex>d_{i}</tex>, следует отметить что всего <tex>t</tex> наборов=См.также==* [[Сортировка подсчетом]]* [[Цифровая сортировка]]

1==Источники информации==* [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) Сортировать все <tex>d_{i}<* [http:/tex> по <tex>d_{i}</tex>dl.value используя bucket sortacm. Пусть все сортированные числа в org/citation.cfm?id=1236460 A[1.Andersson, M. Thorup. Dynamic ordered sets with exponential search trees.r]. Этот шаг занимает линейное время так как сортируется не менее <tex>n^* [[wikipedia:en:Integer_sorting|Wikipedia {{2/5---}}</tex> чисел.Integer sorting]]

2) Поместить все A[j[Категория: Дискретная математика и алгоритмы] в A[j].set