Сортировка Хана

Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью [math]O(n \log\log n)[/math], где [math]n[/math] — количество элементов для сортировки.

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

Алгоритм

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

Andersson's exponential search tree

Э.П.дерево с [math]n[/math] листьями состоит из корня [math]r[/math] и [math]n^e[/math] (0<[math]e[/math]<1) Э.П.поддеревьев, в каждом из которых [math]n^{1 - e}[/math] листьев; каждое Э.П.поддерево является сыном корня [math]r[/math]. В этом дереве [math]O(n \log\log n)[/math] уровней. При нарушении баланса дерева, необходимо балансирование, которое требует [math]O(n \log\log n)[/math] времени при [math]n[/math] вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

Необходимая информация

Определение:

Контейнер — объект определенного типа, содержащий обрабатываемый элемент. Например __int32, __int64, и т.д.

Определение:

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

Определение:

Если мы сортируем целые числа из множества {0, 1, ..., [math]m[/math] - 1} с длиной контейнера [math]k \log (m + n)[/math] с [math]k[/math] >= 1, тогда мы сортируем с неконсервативным преимуществом [math]k[/math].

Определение:

Для множества [math]S[/math] определим [math]\min(S) = \min\limits_{a \in S} a[/math] min([math]S[/math]) = min([math]a[/math]:[math]a[/math] принадлежит [math]S[/math]) max([math]S[/math]) = max([math]a[/math]:[math]a[/math] принадлежит [math]S[/math]) Набор [math]S1[/math] < [math]S2[/math] если max([math]S1[/math]) <= min([math]S2[/math])

Уменьшение числа бит в числах

Один из способов ускорить сортировку — уменьшить число бит в числе. Один из способов уменьшить число бит в числе — использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий [math]O(m)[/math] памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до [math]O(n)[/math]. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования [math]n[/math] чисел в таблицу размера [math]O(n^2)[/math] за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и Raman.

Алгоритм: Пусть целое число [math]b \gt = 0[/math] и пусть [math]U = \{0, \ldots, 2^b - 1\}[/math]. Класс [math]H_{b,s}[/math] хэш функций из [math]U[/math] в [math]\{0, \ldots, 2^s - 1\}[/math] определен как [math]H_{b,s} = \{h_{a} \mid 0 \lt a \lt 2^b, a \equiv 1 (\mod 2)\}[/math] и для всех [math]x[/math] из [math]U: h_{a}(x) = (ax \mod 2^b) div 2^{b - s}[/math].

Данный алгоритм базируется на следующей лемме:

Номер один.

Лемма:

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

Взяв [math]s = 2 \log n[/math] мы получим хэш функцию [math]h_{a}[/math] которая захэширует [math]n[/math] чисел из [math]U[/math] в таблицу размера [math]O(n^2)[/math] без коллизий. Очевидно, что [math]h_{a}(x)[/math] может быть посчитана для любого [math]x[/math] за константное время. Если мы упакуем несколько чисел в один контейнер так, что они разделены несколькими битами нулей, мы спокойно сможем применить [math]h_{a}[/math] ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только (mod [math]2^b[/math]) и (div [math]2^{b - s}[/math]).

Такая хэш функция может быть найдена за [math]O(n^3)[/math].

Следует отметить, что несмотря на размер таблицы [math]O(n^2)[/math], потребность в памяти не превышает [math]O(n)[/math] потому, что хэширование используется только для уменьшения количества бит в числе.

Signature sorting

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

Предположим, что [math]n[/math] чисел должны быть сортированы, и в каждом [math]\log m[/math] бит. Мы рассматриваем, что в каждом числе есть [math]h[/math] сегментов, в каждом из которых [math]\log (m/h)[/math] бит. Теперь мы применяем хэширование ко всем сегментам и получаем [math]2h \log n[/math] бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке [math]n[/math] чисел по [math]m[/math] бит в каждом стала задачей по сортировке [math]n[/math] чисел по [math] \log (m/h)[/math] бит в каждом.

Так же, рассмотрим проблему последующего разделения. Пусть [math]a_{1}[/math], [math]a_{2}[/math], ..., [math]a_{p}[/math] — [math]p[/math] чисел и [math]S[/math] — множество чисeл. Мы хотим разделить [math]S[/math] в [math]p + 1[/math] наборов таких, что: [math]S_{0}[/math] < {[math]a_{1}[/math]} < [math]S_{1}[/math] < {[math]a_{2}[/math]} < ... < {[math]a_{p}[/math]} < [math]S_{p}[/math]. Т.к. мы используем signature sorting, до того как делать вышеописанное разделение, мы поделим биты в [math]a_{i}[/math] на [math]h[/math] сегментов и возьмем некоторые из них. Мы так же поделим биты для каждого числа из [math]S[/math] и оставим только один в каждом числе. По существу для каждого [math]a_{i}[/math] мы возьмем все [math]h[/math] сегментов. Если соответствующие сегменты [math]a_{i}[/math] и [math]a_{j}[/math] совпадают, то нам понадобится только один. Сегменты, которые мы берем для числа в [math]S[/math], — сегмент, который выделяется из [math]a_{i}[/math]. Таким образом мы преобразуем начальную задачу о разделении [math]n[/math] чисел в [math]\log m[/math] бит в несколько задач на разделение с числами в [math]\log (m/h)[/math] бит.

Пример:

[math]a_{1}[/math] = 3, [math]a_{2}[/math] = 5, [math]a_{3}[/math] = 7, [math]a_{4}[/math] = 10, S = {1, 4, 6, 8, 9, 13, 14}.

Мы разделим числа на 2 сегмента. Для [math]a_{1}[/math] получим верхний сегмент 0, нижний 3; [math]a_{2}[/math] верхний 1, нижний 1; [math]a_{3}[/math] верхний 1, нижний 3; [math]a_{4}[/math] верхний 2, нижний 2. Для элементов из S получим: для 1: нижний 1 т.к. он выделяется из нижнего сегмента [math]a_{1}[/math]; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.

Сортировка на маленьких целых

Для лучшего понимания действия алгоритма и материала, изложенного в данной статье, в целом, ниже представлены несколько полезных лемм.

Номер два.

Лемма:

[math]n[/math] целых чисел можно отсортировать в [math]\sqrt{n}[/math] наборов [math]S_{1}[/math], [math]S_{2}[/math], ..., [math]S_{\sqrt{n}}[/math] таким образом, что в каждом наборе [math]\sqrt{n}[/math] чисел и [math]S_{i}[/math] < [math]S_{j}[/math] при [math]i[/math] < [math]j[/math], за время [math]O(n \log\log n/ \log k)[/math] и место [math]O(n)[/math] с не консервативным преимуществом [math]k \log\log n[/math]

Доказательство:

[math]\triangleright[/math]

Доказательство данной леммы будет приведено далее в тексте статьи.

[math]\triangleleft[/math]

Номер три.

Лемма:

Выбор [math]s[/math]-ого наибольшего числа среди [math]n[/math] чисел упакованных в [math]n/g[/math] контейнеров может быть сделана за [math]O(n \log g/g)[/math] время и с использованием [math]O(n/g)[/math] места. Конкретно медиана может быть так найдена.

Доказательство:

[math]\triangleright[/math]

Так как мы можем делать попарное сравнение [math]g[/math] чисел в одном контейнере с [math]g[/math] числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, мы можем упаковать медианы из первого, второго, ..., [math]g[/math]-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом набор [math]S[/math] из медиан теперь содержится в [math]n/(5g)[/math] контейнерах. Рекурсивно находим медиану [math]m[/math] в [math]S[/math]. Используя [math]m[/math] уберем хотя бы [math]n/4[/math] чисел среди [math]n[/math]. Затем упакуем оставшиеся из [math]n/g[/math] контейнеров в [math]3n/4g[/math] контейнеров и затем продолжим рекурсию.

[math]\triangleleft[/math]

Номер четыре.

Лемма:

Если [math]g[/math] целых чисел, в сумме использующие [math](\log n)/2[/math] бит, упакованы в один контейнер, тогда [math]n[/math] чисел в [math]n/g[/math] контейнерах могут быть отсортированы за время [math]O((n/g) \log g)[/math], с использованием [math]O(n/g)[/math] места.

Доказательство:

[math]\triangleright[/math]

Так как используется только [math](\log n)/2[/math] бит в каждом контейнере для хранения [math]g[/math] чисел, мы можем использовать bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает [math]O(n/g)[/math] времени и места. Потому, что мы используем [math](\log n)/2[/math] бит на контейнер нам понадобится [math]\sqrt {n}[/math] шаблонов для всех контейнеров. Затем поместим [math]g \lt (\log n)/2[/math] контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более [math]g - 1[/math] контейнеров которые не смогут образовать группу. Поэтому не более [math]\sqrt{n}(g - 1)[/math] контейнеров не смогут сформировать группу. Для каждой группы мы помещаем [math]i[/math]-е число во всех [math]g[/math] контейнерах в один. Таким образом мы берем [math]g[/math] [math]g[/math]-целых векторов и получаем [math]g[/math] [math]g[/math]-целых векторов где [math]i[/math]-ый вектор содержит [math]i[/math]-ое число из входящего вектора. Эта транспозиция может быть сделана за время [math]O(g \log g)[/math], с использованием [math]O(g)[/math] места. Для всех групп это занимает время [math]O((n/g) \log g)[/math], с использованием [math]O(n/g)[/math] места. Для контейнеров вне групп (которых [math]\sqrt(n)(g - 1)[/math] штук) мы просто разберем и соберем заново контейнеры. На это потребуется не более [math]O(n/g)[/math] места и времени. После всего этого мы используем bucket sorting вновь для сортировки [math]n[/math] контейнеров. таким образом мы отсортируем все числа.

[math]\triangleleft[/math]

Заметим, что когда [math]g = O( \log n)[/math] мы сортируем [math]O(n)[/math] чисел в [math]n/g[/math] контейнеров за время [math]O((n/g) \log\log n)[/math], с использованием O(n/g) места. Выгода очевидна.

Лемма пять.

Лемма:

Если принять, что каждый контейнер содержит [math] \log m \gt \log n[/math] бит, и [math]g[/math] чисел, в каждом из которых [math](\log m)/g[/math] бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий [math](\log n)/(2g)[/math] бит, и [math]g[/math] маркеров упакованы в один контейнер таким же образом[math]^*[/math], что и числа, тогда [math]n[/math] чисел в [math]n/g[/math] контейнерах могут быть отсортированы по их маркерам за время [math]O((n \log\log n)/g)[/math] с использованием [math]O(n/g)[/math] места. (*): если число [math]a[/math] упаковано как [math]s[/math]-ое число в [math]t[/math]-ом контейнере для чисел, тогда маркер для [math]a[/math] упакован как [math]s[/math]-ый маркер в [math]t[/math]-ом контейнере для маркеров.

Доказательство:

[math]\triangleright[/math]

Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует [math]( \log n)/2[/math] бит. Сортировка сгруппирует контейнеры для чисел как в четвертой лемме. Мы можем переместить каждую группу контейнеров для чисел.

[math]\triangleleft[/math]

Заметим, что сортирующие алгоритмы в четвертой и пятой леммах нестабильные. Хотя на их основе можно построить стабильные алгоритмы используя известный метод добавления адресных битов к каждому входящему числу.

Если у нас длина контейнеров больше, сортировка может быть ускорена, как показано в следующей лемме.

Лемма шесть.

Лемма:

предположим, что каждый контейнер содержит [math]\log m \log\log n \gt \log n[/math] бит, что [math]g[/math] чисел, в каждом из которых [math](\log m)/g[/math] бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий [math](\log n)/(2g)[/math] бит, и что [math]g[/math] маркеров упакованы в один контейнер тем же образом что и числа, тогда [math]n[/math] чисел в [math]n/g[/math] контейнерах могут быть отсортированы по своим маркерам за время [math]O(n/g)[/math], с использованием [math]O(n/g)[/math] памяти.

Доказательство:

[math]\triangleright[/math]

Заметим, что несмотря на то, что длина контейнера [math]\log m \log\log n[/math] бит всего [math]\log m[/math] бит используется для хранения упакованных чисел. Так же как в леммах четыре и пять мы сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел мы помещаем [math]g \log\log n[/math] вместо [math]g[/math] контейнеров чисел в одну группу. Для транспозиции чисел в группе содержащей [math]g \log\log n[/math] контейнеров мы сначала упаковываем [math]g \log\log n[/math] контейнеров в [math]g[/math] контейнеров упаковывая [math]\log\log n[/math] контейнеров в один. Далее мы делаем транспозицию над [math]g[/math] контейнерами. Таким образом перемещение занимает всего [math]O(g \log\log n)[/math] времени для каждой группы и [math]O(n/g)[/math] времени для всех чисел. После завершения транспозиции, мы далее распаковываем [math]g[/math] контейнеров в [math]g \log\log n[/math] контейнеров.

[math]\triangleleft[/math]

Заметим, что если длина контейнера [math]\log m \log\log n[/math] и только [math]\log m[/math] бит используется для упаковки [math]g \lt = \log n[/math] чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место [math]O(n/g)[/math], потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время [math]O(n/g)[/math].

Сортировка n целых чисел в sqrt(n) наборов

Постановка задачи и решение некоторых проблем:

Рассмотрим проблему сортировки [math]n[/math] целых чисел из множества {0, 1, ..., [math]m[/math] - 1} в [math]\sqrt{n}[/math] наборов как во второй лемме. Мы предполагаем, что в каждом контейнере [math]k \log\log n \log m[/math] бит и хранит число в [math]\log m[/math] бит. Поэтому неконсервативное преимущество [math]k \log \log n[/math]. Мы так же предполагаем, что [math]\log m \gt = \log n \log\log n[/math]. Иначе мы можем использовать radix sort для сортировки за время [math]O(n \log\log n)[/math] и линейную память. Мы делим [math]\log m[/math] бит, используемых для представления каждого числа, в [math]\log n[/math] блоков. Таким образом каждый блок содержит как минимум [math]\log\log n[/math] бит. [math]i[/math]-ый блок содержит с [math]i \log m/ \log n[/math]-ого по [math]((i + 1) \log m/ \log n - 1)[/math]-ый биты. Биты считаются с наименьшего бита начиная с нуля. Теперь у нас имеется [math]2 \log n[/math]-уровневый алгоритм, который работает следующим образом:

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

Сложная часть алгоритма заключается в том, как поместить маленькие числа в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что [math]n[/math] чисел уже поделены в [math]e[/math] наборов. Мы можем использовать [math]\log e[/math] битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать лемму шесть. Полный размер маркера для каждого контейнера должен быть [math]\log n/2[/math], и маркер использует [math]\log e[/math] бит, количество маркеров [math]g[/math] в каждом контейнере должно быть не более [math]\log n/(2\log e)[/math]. В дальнейшем т.к. [math]g = \log n/(2 \log e)[/math] м.ч. должны влезать в контейнер. Каждый контейнер содержит [math]k \log\log n \log n[/math] блоков, каждое м.ч. может содержать [math]O(k \log n/g) = O(k \log e)[/math] блоков. Заметим, что мы используем неконсервативное преимущество в [math]\log\log n[/math] для использования леммы шесть. Поэтому мы предполагаем что [math]\log n/(2 \log e)[/math] м.ч. в каждом из которых [math]k \log e[/math] блоков битов числа упакованный в один контейнер. Для каждого м.ч. мы используем маркер из [math]\log e[/math] бит, который показывает к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры как и м.ч. Так как каждый контейнер для маркеров содержит [math]\log n/(2 \log e)[/math] маркеров, то для каждого контейнера требуется [math](\log n)/2[/math] бит. Таким образом лемма шесть может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется [math]O((n \log e)/ \log n)[/math] контейнеров то время необходимое для помещения м.ч. в их наборы потребуется [math]O((n \log e)/ \log n)[/math] времени.

Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из леммы шесть.

При таком помещении мы сразу сталкиваемся со следующей проблемой.

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

Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы четыре, пять и шесть расчитанны на не очень маленькие наборы. Но поскольку мы сортируем набор из [math]n[/math] элементов в наборы размера [math]\sqrt{n}[/math], то проблем не должно быть.

Собственно алгоритм:

Algorithm Sort([math]k \log\log n[/math], [math]level[/math], [math]a_{0}[/math], [math]a_{1}[/math], ..., [math]a_{t}[/math])

[math]k \log\log n[/math] это неконсервативное преимущество, [math]a_{i}[/math]-ые это входящие целые числа в наборе, которые надо отсортировать, [math]level[/math] это уровень рекурсии.

1)

[math]if level == 1[/math] тогда изучить размер набора. Если размер меньше или равен [math]\sqrt{n}[/math], то [math]return[/math]. Иначе разделить этот набор в <= 3 набора используя лемму три, чтобы найти медиану а затем использовать лемму 6 для сортировки. Для набора где все элементы равны медиане, не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. [math]Return[/math].

2)

От [math]u = 1[/math] до [math]k[/math]

2.1) Упаковать [math]a^{(u)}_{i}[/math]-ый в часть из [math]1/k[/math]-ых номеров контейнеров, где [math]a^{(u)}_{i}[/math] содержит несколько непрерывных блоков, которые состоят из [math]1/k[/math]-ых битов [math]a_{i}[/math] и у которого текущий блок это самый крупный блок.

2.2) Вызвать Sort([math]k \log\log n[/math], [math]level - 1[/math], [math]a^{(u)}_{0}[/math], [math]a^{(u)}_{1}[/math], ..., [math]a^{(u)}_{t}[/math]). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к которому набору это число относится, уже отправлен назад к месту где число находится во входных данных. Число имеющее наибольшее число бит в [math]a_{i}[/math], показывающее на ткущий блок в нем, так же отправлено назад к [math]a_{i}[/math].

2.3) Отправить [math]a_{i}-ые к их наборам, используя лемму шесть.[/math]

end.

Algorithm IterateSort Call Sort([math]k \log\log n[/math], [math]\log_{k}((\log n)/4)[/math], [math]a_{0}[/math], [math]a_{1}[/math], ..., [math]a_{n - 1}[/math]);

от 1 до 5

начало

Поместить [math]a_{i}[/math] в соответствующий набор с помощью bucket sort потому, что наборов около [math]\sqrt{n}[/math]

Для каждого набора [math]S = [/math]{[math]a_{i_{0}}, a_{i_{1}}, ..., a_{i_{t}}[/math]}, если [math]t \gt sqrt{n}[/math], вызвать Sort([math]k \log\log n[/math], [math]\log_{k}((\log n)/4)[/math], [math]a_{i_{0}}, a_{i_{1}}, ..., a_{i_{t}}[/math])

конец

Время работы алгоритма [math]O(n \log\log n/ \log k)[/math], что доказывает лемму 2.

Собственно сортировка с использованием O(n \log\log n) времени и памяти

Для сортировки [math]n[/math] целых чисел в диапазоне от {[math]0, 1, ..., m - 1[/math]} мы предполагаем, что используем контейнер длины [math]O(\log (m + n))[/math] в нашем консервативном алгоритме. Мы всегда считаем что все числа упакованы в контейнеры одинаковой длины.

Берем [math]1/e = 5[/math] для экспоненциального поискового дереве Андерссона. Поэтому у корня будет [math]n^{1/5}[/math] детей и каждое Э.П.дерево в каждом ребенке будет иметь [math]n^{4/5}[/math] листьев. В отличии от оригинального дерева, мы будем вставлять не один элемент за раз а [math]d^2[/math], где [math]d[/math] — количество детей узла дерева, где числа должны спуститься вниз. Но мы не будем сразу опускать донизу все [math]d^2[/math] чисел. Мы будем полностью опускать все [math]d^2[/math] чисел на один уровень. В корне мы опустим [math]n^{2/5}[/math] чисел на следующий уровень. После того, как мы опустили все числа на следующий уровень мы успешно разделили числа на [math]t_{1} = n^{1/5}[/math] наборов [math]S_{1}, S_{2}, ..., S_{t_{1}}[/math], в каждом из которых [math]n^{4/5}[/math] чисел и [math]S_{i} \lt S_{j}, i \lt j[/math]. Затем мы берем [math]n^{(4/5)(2/5)}[/math] чисел из [math]S_{i}[/math] за раз и опускаем их на следующий уровень Э.П.дерева. Повторяем это, пока все числа не опустятся на следующий уровень. На этом шаге мы разделили числа на [math]t_{2} = n^{1/5}n^{4/25} = n^{9/25}[/math] наборов [math]T_{1}, T_{2}, ..., T_{t_{2}}[/math] в каждом из которых [math]n^{16/25}[/math] чисел, аналогичным наборам [math]S_{i}[/math]. Теперь мы можем дальше опустить числа в нашем Э.П.дереве.

Нетрудно заметить, что ребалансирока занимает [math]O(n \log\log n)[/math] времени с [math]O(n)[/math] временем на уровень. Аналогично стандартному Э.П.дереву Андерссона.

Нам следует нумеровать уровни Э.П.дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне [math]s[/math]. Мы имеем [math]t = n^{1 - (4/5)^s}[/math] наборов по [math]n^{(4/5)^s}[/math] чисел в каждом. Так как каждый узел на данном уровне имеет [math]p = n^{(1/5)(4/5)^s}[/math] детей, то на [math]s + 1[/math] уровень мы опустим [math]q = n^{(2/5)(4/5)^s}[/math] чисел для каждого набора или всего [math]qt \gt = n^{2/5}[/math] чисел для всех наборов за один раз.

Спуск вниз можно рассматривать как сортировку [math]q[/math] чисел в каждом наборе вместе с [math]p[/math] числами [math]a_{1}, a_{2}, ..., a_{p}[/math] из Э.П.дерева, так, что эти [math]q[/math] чисел разделены в [math]p + 1[/math] наборов [math]S_{0}, S_{1}, ..., S_{p}[/math] таких, что [math]S_{0} \lt [/math]{[math]a_{1}[/math]} < ... < {[math]a_{p}[/math]}[math] \lt S_{p}[/math].

Так как нам не надо полностью сортировать [math]q[/math] чисел и [math]q = p^2[/math], есть возможность использовать лемму 2 для сортировки. Для этого нам надо неконсервативное преимущество которое мы получим ниже. Для этого используем линейную технику многократного деления (multi-dividing technique) чтобы добиться этого.

Для этого воспользуемся signature sorting. Адаптируем этот алгоритм для нас. Предположим у нас есть набор [math]T[/math] из [math]p[/math] чисел, которые уже отсортированы как [math]a_{1}, a_{2}, ..., a_{p}[/math], и мы хотим использовать числа в [math]T[/math] для разделения [math]S[/math] из [math]q[/math] чисел [math]b_{1}, b_{2}, ..., b_{q}[/math] в [math]p + 1[/math] наборов [math]S_{0}, S_{1}, ..., S_{p}[/math] что [math]S_{0}[/math] < {[math]a_{1}[/math]} < [math]S_{1}[/math] < ... < {[math]a_{p}[/math]} < [math]S_{p}[/math]. Назовем это разделением [math]q[/math] чисел [math]p[/math] числами. Пусть [math]h = \log n/(c \log p)[/math] для константы [math]c \gt 1[/math]. [math]h/ \log\log n \log p[/math] битные числа могут быть хранены в одном контейнере, так что одно слово хранит [math](\log n)/(c \log\log n)[/math] бит. Сначала рассматриваем биты в каждом [math]a_{i}[/math] и каждом [math]b_{i}[/math] как сегменты одинаковой длины [math]h/ \log\log n[/math]. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки мы хэштруем числа в этих контейнерах ([math]a_{i}[/math]-ом и [math]b_{i}[/math]-ом) чтобы получить [math]h/ \log\log n[/math] хэшированных значений в одном контейнере. Чтобы получить значения сразу, при вычислении хэш значений сегменты не влияют друг на друга, мы можем даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хэш значения считаются за константное время. Затем, посчитав значения мы объединяем два контейнера в один. Пусть [math]a'_{i}[/math] хэш контейнер для [math]a_{i}[/math], аналогично [math]b'_{i}[/math]. В сумме хэш значения имеют [math](2 \log n)/(c \log\log n)[/math] бит. Хотя эти значения разделены на сегменты по [math]h/ \log\log n[/math] бит в каждом контейнере. Между сегментами получаются пустоты, которые мы забиваем нулями. Сначала упаковываем все сегменты в [math](2 \log n)/(c \log\log n)[/math] бит. Потом рассмотрим каждый хэш контейнер как число и отсортируем эти хэш слова за линейное время (сортировка рассмотрена чуть позже). После этой сортировки биты в [math]a_{i}[/math] и [math]b_{i}[/math] разрезаны на [math]\log\log n/h[/math]. Таким образом мы получили дополнительное мультипликативное преимущество в [math]h/ \log\log n[/math] (additional multiplicative advantage).

После того, как мы повторили вышеописанный процесс [math]g[/math] раз мы получили неконсервативное преимущество в [math](h/ \log\log n)^g[/math] раз, в то время как мы потратили только [math]O(gqt)[/math] времени, так как каждое многократное деление делятся за линейное время [math]O(qt)[/math].

Хэш функция, которую мы используем, находится следующим образом. Мы будем хэшировать сегменты, которые [math]\log\log n/h[/math]-ые, [math](\log\log n/h)^2[/math]-ые, ... от всего числа. Для сегментов вида [math](\log\log n/h)^t[/math], получаем нарезанием всех [math]p[/math] чисел на [math](\log\log n/h)^t[/math] сегментов. Рассматривая каждый сегмент как число мы получаем [math]p(\log\log n/h)^t[/math] чисел. Затем получаем одну хэш функцию для этих чисел. Так как [math]t \lt \log n[/math] то мы получим не более [math]\log n[/math] хэш функций.

Рассмотрим сортировку за линейное время о которой было упомянуто ранее. Предполагаем, что мы упаковали хэшированные значения для каждого контейнера в [math](2 \log n)/(c \log\log n)[/math] бит. У нас есть [math]t[/math] наборов в каждом из которых [math]q + p[/math] хэшированных контейнеров по [math](2 \log n)/(c \log\log n)[/math] бит в каждом. Эти числа должны быть отсортированы в каждом наборе. Мы комбинируем все хэш контейнеры в один pool и сортируем следующим образом.

Procedure linear-Time-Sort

Входные данные: [math]r \gt = n^{2/5}[/math] чисел [math]d_{i}[/math], [math]d_{i}[/math].value значение числа [math]d_{i}[/math] в котором [math](2 \log n)/(c \log\log n)[/math] бит, [math]d_{i}.set[/math] набор, в котором находится [math]d_{i}[/math], следует отметить что всего [math]t[/math] наборов.

1) Сортировать все [math]d_{i}[/math] по [math]d_{i}[/math].value используя bucket sort. Пусть все сортированные числа в A[1..r]. Этот шаг занимает линейное время так как сортируется не менее [math]n^{2/5}[/math] чисел.

2) Поместить все A[j] в A[j].set

Таким образом мы заполнили все наборы за линейное время.

Как уже говорилось ранее после [math]g[/math] сокращений бит мы получили неконсервативное преимущество в [math](h/ \log\log n)^g[/math]. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на лемму два для завершения разделения [math]q[/math] чисел с помощью [math]p[/math] чисел на наборы. Заметим, что по природе битового сокращения, начальная задача разделения для каждого набора перешла в [math]w[/math] подзадачи разделения на [math]w[/math] поднаборы для какого-то числа [math]w[/math].

Теперь для каждого набора мы собираем все его поднаборы в подзадачах в один набор. Затем используя лемму два делаем разделение. Так как мы имеем неконсервативное преимущество в [math](h/ \log\log n)^g[/math] и мы работаем на уровнях не ниже чем [math]2 \log\log\log n[/math], то алгоритм занимает [math]O(qt \log\log n/(g(\log h - \log\log\log n) - \log\log\log n)) = O(\log\log n)[/math] времени.

Мы разделили [math]q[/math] чисел [math]p[/math] числами в каждый набор. То есть мы получили [math]S_{0}[/math] < {[math]e_{1}[/math]} < [math]S_{1}[/math] < ... < {[math]e_{p}[/math]} < [math]S_{p}[/math], где [math]e_{i}[/math] это сегмент [math]a_{i}[/math] полученный с помощью битового сокращения. Мы получили такое разделение комбинированием всех поднаборов в подзадачах. Предположим числа хранятся в массиве [math]B[/math] так, что числа в [math]S_{i}[/math] предшествуют числам в [math]S_{j}[/math] если [math]i \lt j[/math] и [math]e_{i}[/math] хранится после [math]S_{i - 1}[/math] но до [math]S_{i}[/math]. Пусть [math]B[i][/math] в поднаборе [math]B[i].subset[/math]. Чтобы позволить разделению выполнится для каждого поднабора мы делаем следующее.

Помещаем все [math]B[j][/math] в [math]B[j].subset[/math]

На это потребуется линейное время и место.

Теперь рассмотрим проблему упаковки, которую решим следующим образом. Будем считать что число бит в контейнере [math]\log m \gt = \log\log\log n[/math], потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть [math]h/ \log\log n[/math] хэшированных значений (сегментов) в себе на уровне [math]\log h[/math] в Э.П.дереве. Полное число хэшированных бит в контейнере [math](2 \log n)(c \log\log n)[/math] бит. Хотя хэшированны биты в контейнере выглядят как [math]0^{i}t_{1}0^{i}t_{2}...t_{h/ \log\log n}[/math], где [math]t_{k}[/math]-ые это хэшированные биты, а нули это просто нули. Сначала упаковываем [math]\log\log n[/math] контейнеров в один и получаем [math]w_{1} = 0^{j}t_{1, 1}t_{2, 1}...t_{\log\log n, 1}0^{j}t_{1, 2}...t_{\log\log n, h/ \log\log n}[/math] где [math]t_{i, k}[/math]: [math]k = 1, 2, ..., h/ \log\log n[/math] из [math]i[/math]-ого контейнера. мы ипользуем [math]O(\log\log n)[/math] шагов, чтобы упаковать [math]w_{1}[/math] в [math]w_{2} = 0^{jh/ \log\log n}t_{1, 1}t_{2, 1} ... t_{\log\log n, 1}t_{1, 2}t_{2, 2} ... t_{1, h/ \log\log n}t_{2, h/ \log\log n} ... t_{\log\log n, h/ \log\log n}[/math]. Теперь упакованные хэш биты занимают [math]2 \log n/c[/math] бит. Мы используем [math]O(\log\log n)[/math] времени чтобы распаковать [math]w_{2}[/math] в [math]\log\log n[/math] контейнеров [math]w_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, 1}O^{r}t_{k, 2} ... t_{k, h/ \log\log n} k = 1, 2, ..., \log\log n[/math]. Затем используя [math]O(\log\log n)[/math] времени упаковываем эти [math]\log\log n[/math] контейнеров в один [math]w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} ... t_{1, h/ \log\log n}0^{r}t_{2, 1} ... t_{\log\log n, h/ \log\log n}[/math]. Затем используя [math]O(\log\log n)[/math] шагов упаковать [math]w_{4}[/math] в [math]w_{5} = 0^{s}t_{1, 1}t_{1, 2} ... t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} ... t_{\log\log n, h/ \log\log n}[/math]. В итоге мы используем [math]O(\log\log n)[/math] времени для упаковки [math]\log\log n[/math] контейнеров. Считаем что время потраченное на одно слово — константа.

Вывод

Таким образом имеем:

Теорема:

[math]n[/math] целых чисел могут быть отсортированы за время [math]O(n \log\log n)[/math] и линейную память.

Литераура

Deterministic Sorting in O(n \log\log n) Time and Linear Space. Yijie Han.