Изменения

'''Сортировка Хана ''' (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 Экспоненциальное поисковое дерево Андерсона ==

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

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

2) Каждое поддерево корня имеет <texdpi="130">\Theta(n^{1-e})</tex> сыновей.

В этом дереве <texdpi="130">O(n \log\log n)</tex> уровней. При нарушении баланса дерева необходимо балансирование, которое требует <texdpi="130">O(n \log\log n)</tex> времени при <texdpi="130">n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон.

Алгоритм, сортирующий <texdpi="130">n</tex> целых чисел из множества <texdpi="130">\{0, 1, \ldots, m - 1\}</tex>, называется '''консервативным''', если длина контейнера (число бит в контейнере) равна <texdpi="130">O(\log(m + n))</tex>. Если длина больше, то алгоритм '''неконсервативный'''.

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

Для множества <texdpi="130">S</tex> определим

<texdpi="130">\min(S) = \min\limits_{a \in S} a</tex>

<texdpi="130">\max(S) = \max\limits_{a \in S} a</tex>

Набор <texdpi="130">S1</tex> < <tex>S2</tex> если <texdpi="130">\max(S1) \le leqslant \min(S2)</tex>

Предположим, есть набор <texdpi="130">T</tex> из <texdpi="130">p</tex> чисел, которые уже отсортированы как <texdpi="130">a_{1}, a_{2}, \ldots, a_{p}</tex> и набор <texdpi="130">S</tex> из <texdpi="130">q</tex> чисел <texdpi="130">b_{1}, b_{2}, \ldots, b_{q}</tex>. Тогда '''разделением''' <texdpi="130">q</tex> чисел <texdpi="130">p</tex> числами называется <texdpi="130">p + 1</tex> набор <texdpi="130">S_{0}, S_{1}, \ldots, S_{p}</tex>, где <texdpi="130">S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>.

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

Выбор <texdpi="130">s</tex>-ого наибольшего числа среди <texdpi="130">n</tex> чисел, упакованных в <texdpi="150">\frac{n/}{g}</tex> контейнеров, может быть сделан за время <texdpi="150">O(\frac{n \log g/}{g})</tex> и с использованием <texdpi="150">O(\frac{n/}{g})</tex> памяти. В том числе, так может быть найдена медиана.

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

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

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

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

Заметим, что когда <texdpi="130">g = O( \log n)</tex>, сортировка <texdpi="130">O(n)</tex> чисел в <texdpi="150">\frac{n/}{g}</tex> контейнеров произойдет за время <texdpi="150">O((\frac{n/}{g}) </tex> <tex dpi="130">\log\log n)</tex> с использованием <texdpi="150">O(\frac{n/}{g})</tex> памяти. Выгода очевидна.

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

Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <texdpi="150">( \frac{\log n)/}{2}</tex> бит. Сортировка сгруппирует контейнеры для чисел как в [[#lemma3|лемме №3]]. Перемещаем каждую группу контейнеров для чисел.

Предположим, что каждый контейнер содержит <texdpi="130">\log m \log\log n > \log n</tex> бит, что <texdpi="130">g</tex> чисел, в каждом из которых <texdpi="150">(\frac{\log m)/}{g}</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <texdpi="150">(\frac{\log n)/(}{2g)}</tex> бит, и что <texdpi="130">g</tex> маркеров упакованы в один контейнер тем же образом что и числа. Тогда <texdpi="130">n</tex> чисел в <texdpi="150">\frac{n/}{g}</tex> контейнерах могут быть отсортированы по своим маркерам за время <texdpi="150">O(\frac{n/}{g})</tex> с использованием <texdpi="150">O(\frac{n/}{g})</tex> памяти.

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

Заметим, что если длина контейнера <texdpi="130">\log m \log\log n</tex> и только <texdpi="130">\log m</tex> бит используется для упаковки <texdpi="130">g \le leqslant \log n</tex> чисел в один контейнер, тогда выбор в [[#lemma2|лемме №2]] может быть сделан за время и память <texdpi="150">O(\frac{n/}{g})</tex>, потому что упаковка в доказательстве [[#lemma2|лемме №2]] теперь может быть сделана за время <texdpi="150">O(\frac{n/}{g})</tex>.

<texdpi="130">n</tex> целых чисел можно отсортировать в <texdpi="130">\sqrt{n}</tex> наборов <texdpi="130">S_{1}</tex>, <texdpi="130">S_{2}</tex>, <texdpi="130">\ldots</tex>, <texdpi="130">S_{\sqrt{n}}</tex> таким образом, что в каждом наборе <texdpi="130">\sqrt{n}</tex> чисел и <texdpi="130">S_{i}</tex> < <tex>S_{j}</tex> при <texdpi="130">i</tex> < <tex>j</tex>, за время <texdpi="150">O(\frac{n \log\log n/ } {\log k})</tex> и место <texdpi="130">O(n)</tex> с неконсервативным преимуществом <texdpi="130">k \log\log n</tex>.

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

Рассмотрим проблему сортировки <texdpi="130">n</tex> целых чисел из множества <texdpi="130">\{0, 1, \ldots, m - 1\}</tex> в <texdpi="130">\sqrt{n}</tex> наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит <texdpi="130">k \log\log n \log m</tex> бит и хранит число в <texdpi="130">\log m</tex> бит. Поэтому неконсервативное преимущество {{---}} <texdpi="130">k \log \log n</tex>. Также предполагаем, что <texdpi="130">\log m \ge geqslant \log n \log\log n</tex>. Иначе можно использовать radix sort для сортировки за время <texdpi="130">O(n \log\log n)</tex> и линейную память. Делим <texdpi="130">\log m</tex> бит, используемых для представления каждого числа, в <texdpi="130">\log n</tex> блоков. Таким образом, каждый блок содержит как минимум <texdpi="130">\log\log n</tex> бит. <texdpi="130">i</tex>-ый блок содержит с <texdpi="150">\frac{i \log m/ } {\log n}</tex>-ого по <texdpi="150">(\frac{(i + 1) \log m/ } {\log n - 1})</tex>-ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <texdpi="130">2 \log n</tex>-уровневый алгоритм, который работает следующим образом:

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

Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <texdpi="130">n</tex> чисел уже поделены в <texdpi="130">e</tex> наборов. Используем <texdpi="130">\log e</tex> битов чтобы сделать марки для каждого набора. Теперь используем [[#lemma5|лемме №5]]. Полный размер маркера для каждого контейнера должен быть <texdpi="150">\frac{\log n/}{2}</tex>, и маркер использует <texdpi="130">\log e</tex> бит, значит количество маркеров <texdpi="130">g</tex> в каждом контейнере должно быть не более <texdpi="150">\frac{\log n/(}{2\log e)}</tex>. В дальнейшем, так как <texdpi="150">g = \frac{\log n/(}{2 \log e)}</tex>, м.ч. должны влезать в контейнер. Каждый контейнер содержит <texdpi="130">k \log\log n \log n</tex> блоков, каждое м.ч. может содержать <texdpi="150">O(\frac{k \log n/}{g}) = O(k \log e)</tex> блоков. Заметим, что используется неконсервативное преимущество в <texdpi="130">\log\log n</tex> для [[#lemma5|лемме №5]] Поэтому предполагается, что <texdpi="150">\frac{\log n/(}{2 \log e)}</tex> м.ч., в каждом из которых <texdpi="130">k \log e</tex> блоков битов числа, упакованны в один контейнер. Для каждого м.ч. используется маркер из <texdpi="130">\log e</tex> бит, который показывает, к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры, как и м.ч. Так как каждый контейнер для маркеров содержит <texdpi="150">\frac{\log n/(}{2 \log e)}</tex> маркеров, то для каждого контейнера требуется <texdpi="150">(\frac{\log n)/}{2}</tex> бит. Таким образом, [[#lemma5|лемма №5]] может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <texdpi="150">O((\frac{n \log e)/ }{ \log n})</tex> контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно <texdpi="150">O((\frac{n \log e)/ }{ \log n})</tex>.

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

Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы [[#lemma3|3]], [[#lemma4|4]], [[#lemma5|5]] расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <texdpi="130">n</tex> элементов в наборы размера <texdpi="130">\sqrt{n}</tex>, то проблем быть не должно.

Algorithm Sort(<tex>k \log\log nadvantage</tex>, {{---}} это неконсервативное преимущество равное <tex>levelk\log\log n</tex>, <tex>a_{0i}</tex>-ые это входящие целые числа в наборе, <tex>a_{1}</tex>которые надо отсортировать, <tex>\ldots</tex>, <tex>a_{t}level</tex>)это уровень рекурсии.

<tex>k \log\log n</tex> {{---}} это неконсервативное преимущество, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, # Если <tex>level</tex> это уровень рекурсии. # Если равен <tex>(level == 1)</tex> тогда изучаем размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе делим этот набор в <tex>\leleqslant</tex> 3 набора, используя [[#lemma2|лемму №2]], чтобы найти медиану, а затем используем [[#lemma5|лемму №5]] для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.# От <texdpi="130">u = 1</tex> до <texdpi="130">k</tex>## Упаковываем <texdpi="130">a^{(u)}_{i}</tex>-ый в часть из <texdpi="130">1/k</tex>-ых номеров контейнеров. Где <texdpi="130">a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <texdpi="150">\frac{1/}{k}</tex>-ых битов <texdpi="130">a_{i}</tex>. При этом у <texdpi="130">a^{(u)}_{i}</tex> текущий блок это самый крупный блок.## Вызываем Sort(<tex>k \log\log nSort(advantage</tex>, <tex>level - 1</tex>, <texdpi="130">a^{(u)}_{0}</tex>, <texdpi="130">a^{(u)}_{1}</tex>, <tex>\ldots</tex>, <texdpi="130">a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к какому набору это число относится, уже направлен назад к месту, где число находится во входных данных. Число, имеющее наибольшее число бит в <texdpi="130">a_{i}</tex>, показывающее на текущий блок в нем, так же направлено назад к <texdpi="130">a_{i}</tex>.## Отправляем <texdpi="130">a_{i}</tex>-ые к их наборам, используя [[#lemma5|лемму №5]].

Call Sort(<tex>k \log\log nSort(advantage</tex>, <texdpi="130">\log_{k}((\log n)/4)</tex>, <texdpi="130">a_{0}</tex>, <texdpi="130">a_{1}</tex>, <texdpi="130">\ldots</tex>, <texdpi="130">a_{n - 1}</tex>);

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

Время работы алгоритма <texdpi="150">O(\frac{n \log\log n/ }{\log k})</tex>, что доказывает лемму.

Берем <tex>1/e = 5</tex> для ЭП-дерева Андерссона. Следовательно, у корня будет <tex>n^{1/5}</tex> детей, и каждое ЭП-дерево =Уменьшение числа бит в каждом ребенке будет иметь <tex>n^{4/5}</tex> листьев. В отличие от оригинального дерева, зараз вставляется не один элемент, а <tex>d^2</tex>, где <tex>d</tex> — количество детей узла дерева, в котором числа должны спуститься вниз. Алгоритм полностью опускает все <tex>d^2</tex> чисел на один уровень. В корне опускаются <tex>n^{2/5}</tex> чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на <tex>t_{1} числах== n^Один из способов ускорить сортировку {1/5}</tex> наборов <tex>S_{1---}, S_{2}, \ldots, S_{t_{1}}</tex>, уменьшить число бит в каждом числе. Один из которых <tex>n^способов уменьшить число бит в числе {4/5}</tex> чисел и <tex>S_{i---} < S_{j}использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, i < j</tex>что количество оставшихся бит в числе уменьшается в 2 раза. ЗатемЭто быстрый способ, берутся требующий <texdpi="130">n^{O(4/5m)(2/5)}</tex> чисел из <tex>S_{i}</tex> и опускаются на следующий уровень ЭП-памяти. Для своего дерева. Это повторяетсяАндерссон использует хеширование, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на что позволяет сократить количество памяти до <texdpi="130">t_{2} = O(n^{1/5}n^{4/25} = n^{9/25})</tex> наборов <tex>T_{1}. Для того чтобы еще ускорить алгоритм, T_{2}необходимо упаковать несколько чисел в один контейнер, \ldotsчтобы затем за константное количество шагов произвести хеширование для всех чисел, T_{t_{2}}хранимых в контейнере. Для этого используется хеш-функция для хеширования </texdpi="130">, аналогичных наборам <tex>S_{i}n</tex>, чисел в каждом из которых таблицу размера <texdpi="130">O(n^{16/25}2)</tex> чиселза константное время без коллизий. Теперь числа опускаются дальше в ЭПДля этого используется модифицированная хеш-деревефункция авторства: Dierzfelbinger и Raman.

Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз Данный алгоритм базируется на уровне <tex>s</tex>. Имеется <tex>t = n^{1 - (4/5)^s}</tex> наборов по <tex>n^{(4/5)^s}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет <tex>p = n^{(1/5)(4/5)^s}</tex> детей, то на <tex>s + 1</tex> уровень опускаются <tex>q = n^{(2/5)(4/5)^s}</tex> чисел для каждого набора, или всего <tex>qt \ge n^{2/5}</tex> чисел для всех наборов за один раз[[#lemma1|лемме №1]].

Спуск вниз можно рассматривать как сортировку Взяв <texdpi="130">qs = 2 \log n</tex> чисел в каждом наборе вместе с <tex>p, получаем хеш-функцию </texdpi="130"> числами <tex>a_{1}, a_{2}, \ldots, a_h_{pa}</tex> из ЭП-дерева, так, что эти которая захеширует <texdpi="130">qn</tex> чисел разделены в из <texdpi="130">p + 1U</tex> наборов в таблицу размера <texdpi="130">S_{0}, S_{1}, \ldots, S_{p}O(n^2)</tex> такихбез коллизий. Очевидно, что <texdpi="130">S_h_{0a} < (x)</tex> {может быть посчитана для любого <texdpi="130">a_{1}x</tex>} за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить <texdpi="130"><h_{a}</tex> ко всему контейнеру, и в результате все хеш-значения для всех чисел в контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-значения вовлечены только (<texdpi="130">\ldotsbmod</tex> <texdpi="130"><2^b</tex> {) и (<texdpi="130">a_{p}div</tex>} <texdpi="130">< S_2^{pb - s}</tex>).

Так как Такая хеш-функция может быть найдена за <texdpi="130">q</tex> чисел не надо полностью сортировать и <tex>q = pO(n^23)</tex>, то можно использовать [[#lemma6|лемму №6]] для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с помощью signature sorting. Для этого используется линейная техника многократного деления (multi-dividing technique).

После ==Сортировка по ключу==Предположим, что <tex dpi="130">n</tex> чисел должны быть отсортированы, и в каждом <texdpi="130">g\log m</tex> сокращений бит . Будем считать, что в '''signature sorting''' получаем неконсервативное преимущество в каждом числе есть <texdpi="130">(h</ tex> сегментов, в каждом из которых <tex dpi="130">\log</tex> <tex dpi="150">\frac{m}{h}</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex dpi="130">2h \log n)^g</tex>бит хешированных значений для каждого числа. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться После сортировки на [[#lemma6|лемму №6]] хешированных значениях для завершения разделения всех начальных чисел начальная задача по сортировке <texdpi="130">qn</tex> чисел с помощью по <texdpi="130">p\log m</tex> чисел на наборы. Заметим, что бит в каждом стала задачей по природе битового сокращения начальная задача разделения для каждого набора перешла в сортировке <texdpi="130">wn</tex> подзадач разделения на чисел по <texdpi="130">w\log</tex> поднаборов для какого-то числа <texdpi="150">w\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> наборов, используя [[#lemma6|лемму №6]]таких, делается разделениечто: <tex dpi="130">S_{0} < a_{1} < S_{1} < a_{2} < \ldots < a_{p} < S_{p}</tex>. Так как получено неконсервативное преимущество используется '''сортировка по ключу''' (англ. ''signature sorting'') то перед тем, как делать вышеописанное разделение, необходимо поделить биты в <texdpi="130">a_{i}</tex> на <tex dpi="130">(h</ \log\log n)^gtex> сегментов и взять некоторые из них. Так же делим биты для каждого числа из <tex dpi="130">S</tex> и работа происходит на уровнях не нижеоставляем только один в каждом числе. По существу, чем для каждого <tex dpi="130">a_{i}</tex> берутся все <tex dpi="130">h</tex> сегментов. Если соответствующие сегменты <tex dpi="130">a_{i}</tex> и <texdpi="130">2 \log\log\log na_{j}</tex>совпадают, то алгоритм занимает нам понадобится только один. Сегмент, который берется для числа в <tex dpi="130">S</tex>O(qt \log\log это сегмент, который выделяется из <tex dpi="130">a_{i}</tex>. Таким образом, начальная задача о разделении <tex dpi="130">n</(g(tex> чисел по <tex dpi="130">\log h - \log\log\log n) - \log\log\log n)) m</tex> бит преобразуется в несколько задач на разделение с числами по <tex dpi= O("150">\logfrac{\log n)m}{h}</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>, полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, что числа хранятся в массиве <tex>B</tex> так, что числа в <tex>S_{i}</tex> предшествуют числам в <tex>S_{j}</tex> если <tex>i < j</tex> и <tex>e_{i}</tex> хранится после <tex>S_{i '''Пример''':[[Файл:Han- 1}</tex>, но до <tex>S_{i}</tex>example. png|500px|thumb]]

Пусть Делим числа на два сегмента. Для <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>; <texdpi="130">B[i]a_{4}</tex> находится в поднаборе {{---}} верхний <tex dpi="130">2</tex>, нижний <tex dpi="130">2</tex>B[i].subsetДля элементов из 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> и <texdpi="130">B[j]3</tex> в , нижние сегменты <texdpi="130">B[j].subset4, 5, 6, 7,</tex> нижние сегменты <tex dpi="130">8, 9, 10</tex> формируют <tex dpi="130">4</tex>новые задачи на разделение.

Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex>\log m \ge \log\log\log n</tex>, потому что в противном случае можно использовать radix sort для Использование '''сортировки чисел. У контейнера есть <tex>h/ \log\log n</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_{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/c</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}0^{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 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} использовать деление пополам (эту идею впервые подал van Emde Boas</tex>). Деление пополам заключается -битные числа могут храниться в томодном контейнере, что количество оставшихся содержащим <tex dpi="150">\frac{\log n}{c \log\log n}</tex> бит . Сначала рассматриваем биты в числе уменьшается в 2 разакаждом <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>-ом и <texdpi="130">O(m)b_{i}</tex> памяти. Для своего дерева Андерссон использует хеширование-ом) хешируются, что позволяет сократить количество памяти до и получается <texdpi="150">O(\frac{h}{\log\log n)}</tex>хешированных значений в одном контейнере. Для того чтобы еще ускорить алгоритмПри вычислении хеш-значений сегменты не влияют друг на друга, необходимо упаковать несколько чисел можно даже отделить четные и нечетные сегменты в один контейнердва контейнера. Не умаляя общности считаем, чтобы затем что хеш-значения считаются за константное количество шагов произвести хеширование для всех чиселвремя. Затем, посчитав значения, хранимых два контейнера объединяем в контейнереодин. Для этого используется Пусть <tex dpi="130">a'_{i}</tex> {{---}} хеш-функция контейнер для хеширования <texdpi="130">a_{i}</tex>, аналогично <tex dpi="130">b'_{i}</tex>. В сумме хеш-значения имеют <tex dpi="150">\frac{2 \log n}{c \log\log n}</tex> бит, хотя эти значения разделены на сегменты по <tex dpi="150">\frac{h}{ \log\log n}</tex> чисел бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в таблицу размера <texdpi="150">O(\frac{2 \log n}{c \log\log n^2)}</tex> бит. Потом рассматривается каждый хеш-контейнер как число, и эти хеш-контейнеры сортируются за константное линейное время без коллизий(сортировка будет рассмотрена чуть позже). Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger После этой сортировки биты в <tex dpi="130">a_{i}</tex> и Raman<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="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> чисел на [[#lemma1|лемме №1]]<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> хеш-функций.

Взяв Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в <texdpi="150">s = \frac{2 \log n</tex>, получаем хеш-функцию <tex>h_}{ac \log\log n}</tex>, которая захеширует бит. Есть <texdpi="130">nt</tex> чисел наборов, в каждом из которых <texdpi="130">Uq + p</tex> в таблицу размера хешированных контейнеров по <texdpi="150">O(\frac{2 \log n^2)</tex> без коллизий. Очевидно, что <tex>h_}{ac \log\log n}(x)</tex> может бит в каждом. Эти контейнеры должны быть посчитана для любого <tex>x</tex> за константное времяотсортированы в каждом наборе. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить <tex>h_{a}</tex> ко всему контейнеру, и в результате Комбинируя все хеш-значения для всех чисел контейнеры в контейнере будут посчитаны. Заметимодин pool, что это возможно только потому, что в вычисление хеш-значения вовлечены только (<tex>\bmod</tex> <tex>2^b</tex>) и (<tex>div</tex> <tex>2^{b - s}</tex>)сортируем следующим образом.

Такая хеш-функция может быть найдена Операция '''сортировки за <tex>Oлинейное время''' (n^3англ. ''Linear-Time-Sort'')</tex>.

Следует отметить, что, несмотря на размер таблицы Входные данные: <texdpi="150">O(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>, потребность в памяти не превышает котором <texdpi="150">O(\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> наборов.

==Signature sorting==Предположим, что # Сортируем все <texdpi="130">nd_{i}</tex> чисел должны быть отсортированы, и в каждом по <texdpi="130">\log m</tex> битd_{i}. Будем считаем, что в каждом числе есть <tex>hvalue</tex> сегментов, используя bucket sort. Пусть все отсортированные числа в каждом из которых <texdpi="130">\log m/h</tex> битA[1.. Теперь применяем хеширование ко всем сегментам и получаем <tex>2h \log nr]</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке Этот шаг занимает линейное время, так как сортируется не менее <texdpi="150">n^{\frac{2}{5}}</tex> чисел по .# Помещаем все <texdpi="130">\log mA[j]</tex> бит в каждом стала задачей по сортировке <texdpi="130">n</tex> чисел по <tex>\log m/hA[j].set</tex> бит в каждом.

Делим числа Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на 2 сегментауровне <tex dpi="130">s</tex>. Для Имеется <texdpi="150">a_t = n^{1- (\frac{4}{5})^S}</tex> получим верхний сегмент 0, нижний 3; наборов по <texdpi="150">a_n^{(\frac{24}{5})^S}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет <tex dpi="150">p = n^{\frac{1}{---5} \cdot (\frac{4}{5})^S} верхний 1</tex> детей, нижний то на <tex dpi="130">s + 1; </tex>a_{3}уровень опускаются </texdpi="150"> q = n^{\frac{---2}{5} верхний 1, нижний 3; <tex>a_\cdot (\frac{4}{5})^S}</tex> {{---}} верхний 2, нижний 2. Для элементов из S получим: чисел для 1 нижний 1каждого набора, так как он выделяется из нижнего сегмента или всего <texdpi="150">a_qt \geqslant n^{\frac{2}{15}}</tex>; для 4 нижний 0; чисел для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделениевсех наборов за один раз.

Использование '''signature sorting''' Спуск вниз можно рассматривать как сортировку <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>.

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

Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, После <texdpi="130">\log\log n/hg</tex>-ые, сокращений бит в [[Сортировка Хана#Signature sorting|signature sorting]] получаем неконсервативное преимущество в <texdpi="150">(\frac{h}{ \log\log n/h})^2g</tex>-ые. Мы не волнуемся об этих сокращениях до конца потому, <tex>\ldots</tex> по счету в числе. Хеш-функцию что после получения неконсервативного преимущества мы можем переключиться на [[#lemma6|лемму №6]] для завершения разделения <texdpi="130">(\log\log n/h)^tq</tex>-ых по счету сегментов, получаем нарезанием всех чисел с помощью <texdpi="130">p</tex> чисел на <tex>(\log\log n/h)^t</tex> сегментовнаборы. Рассматривая каждый сегмент как числоЗаметим, получаем что по природе битового сокращения начальная задача разделения для каждого набора перешла в <texdpi="130">p(\log\log n/h)^tw</tex> чисел. Затем получаем одну хеш-функцию для этих чисел. Так как подзадач разделения на <texdpi="130">t < \log nw</tex>, поднаборов для какого-то получится не более числа <texdpi="130">\log nw</tex> хеш-функций.

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

Procedure '''LinearВ итоге разделились <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> {{-Time-Sort'''-}} сегмент <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>.

# Сортируем все Пусть <texdpi="130">d_{B[i}]</tex> по <tex>d_{i}.value</tex>, используя bucket sort. Пусть все отртированные числа находится в поднаборе <texdpi="130">AB[1.i].r]subset</tex>. Этот шаг занимает линейное времяЧтобы позволить разделению выполниться, так как сортируется не менее <tex>n^{2/5}</tex> чисел.# Помещаем для каждого поднабора помещаем все <texdpi="130">AB[j]</tex> в <texdpi="130">AB[j].setsubset</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]]

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