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

Сортировка Хана (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] ([math]0\lt e \lt 1[/math]) ЭП-поддеревьев, в каждом из которых [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] вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

Определения

1. Контейнер — объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.
2. Алгоритм сортирующий [math]n[/math] целых чисел из множества [math]\{0, 1, \ldots, m - 1\}[/math] называется консервативным, если длина контейнера (число бит в контейнере), является [math]O(\log(m + n))[/math]. Если длина больше, то алгоритм неконсервативный.
3. Если сортируются целые числа из множества [math]\{0, 1, \ldots, m - 1\}[/math] с длиной контейнера [math]k \log (m + n)[/math] с [math]k[/math] [math]\ge[/math] 1, тогда сортировка происходит с неконсервативным преимуществом [math]k[/math].
4. Для множества [math]S[/math] определим

[math]\min(S) = \min\limits_{a \in S} a[/math]

[math]\max(S) = \max\limits_{a \in S} a[/math]

Набор [math]S1[/math] < [math]S2[/math] если [math]\max(S1) \le \min(S2)[/math]

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

Для сортировки [math]n[/math] целых чисел в диапазоне от {[math]0, 1, \ldots, 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]n^{2/5}[/math] чисел на следующий уровень. После того, как опустились все числа на следующий уровень и они успешно разделились на [math]t_{1} = n^{1/5}[/math] наборов [math]S_{1}, S_{2}, \ldots, 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}, \ldots, 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 \ge n^{2/5}[/math] чисел для всех наборов за один раз.

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

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

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

Теперь для каждого набора собираются все его поднаборы в подзадачах в один набор. Затем используя лемму №2, делается разделение. Так как получено неконсервативное преимущество в [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]\ldots[/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 \ge \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} \ldots 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} \ldots t_{\log\log n, 1}0^{j}t_{1, 2} \ldots t_{\log\log n, h/ \log\log n}[/math] где [math]t_{i, k}[/math]: [math]k = 1, 2, \ldots, 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} \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}[/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} \ldots t_{k, h/ \log\log n} k = 1, 2, \ldots, \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} \ldots t_{1, h/ \log\log n}0^{r}t_{2, 1} \ldots 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} \ldots t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} \ldots t_{\log\log n, h/ \log\log n}[/math]. В итоге используем [math]O(\log\log n)[/math] времени для упаковки [math]\log\log n[/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 \ge 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 (\bmod 2)\}[/math] и для всех [math]x[/math] из [math]U: h_{a}(x) = (ax[/math] [math]\bmod[/math] [math]2^b)[/math] [math]div[/math] [math]2^{b - s}[/math].

Данный алгоритм базируется на лемме №1.

Взяв [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] ко всему контейнеру, а в результате все хеш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хеш знчения вовлечены только ([math]\bmod[/math] [math]2^b[/math]) и ([math]div[/math] [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]\ldots[/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]\ldots[/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 = [math]\{1, 4, 6, 8, 9, 13, 14\}[/math].

Делим числа на 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 новые задачи на разделение.

Использование signature sorting в данном алгоритме:

Предположим у нас есть набор [math]T[/math] из [math]p[/math] чисел, которые уже отсортированы как [math]a_{1}, a_{2}, \ldots, a_{p}[/math], и хотется использовать числа в [math]T[/math] для разделения [math]S[/math] из [math]q[/math] чисел [math]b_{1}, b_{2}, \ldots, b_{q}[/math] в [math]p + 1[/math] наборов [math]S_{0}, S_{1}, \ldots, S_{p}[/math] что [math]S_{0}[/math] < {[math]a_{1}[/math]} < [math]S_{1}[/math] < [math]\ldots[/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]\ldots[/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, сортируем следующим образом.

Лемма №1

Даны целые числа [math]b[/math] [math]\ge[/math] [math]s[/math] [math]\ge[/math] 0 и [math]T[/math] является подмножеством [math]\{0, \ldots, 2^b - 1\}[/math], содержащим [math]n[/math] элементов, и [math]t[/math] [math]\ge[/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)[/math] [math]\le[/math] t</tex>

Лемма №2

[math]n[/math] целых чисел можно отсортировать в [math]\sqrt{n}[/math] наборов [math]S_{1}[/math], [math]S_{2}[/math], [math]\ldots[/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]n[/math] целых чисел в [math]\sqrt{n}[/math] наборов, представленный ниже, является доказательством данной леммы.

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

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

Рассмотрим проблему сортировки [math]n[/math] целых чисел из множества [math]\{0, 1, \ldots, m - 1\}[/math] в [math]\sqrt{n}[/math] наборов как в лемме №2. Предполагая, что в каждом контейнере [math]k \log\log n \log m[/math] бит и хранит число в [math]\log m[/math] бит. Поэтому неконсервативное преимущество [math]k \log \log n[/math]. Так же предполагаем, что [math]\log m \ge \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] м.ч. упакованных в один контейнер. Пренебрегая временем, потраченным на на эту упаковку, считается, что она бесплатна. По лемме №3 находим медиану этих [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]\le [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] битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать лемму №6. Полный размер маркера для каждого контейнера должен быть [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] для использования леммы №6. Поэтому предполагается, что [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] бит. Таким образом лемма №6 может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется [math]O((n \log e)/ \log n)[/math] контейнеров то время необходимое для помещения м.ч. в их наборы потребуется [math]O((n \log e)/ \log n)[/math] времени.

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

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

Рассмотрим число [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] блоках.

Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы №4, №5, №6 расчитанны на не очень маленькие наборы. Но поскольку сортируется набор из [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]\ldots[/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]. Иначе разделить этот набор в [math]\le[/math] 3 набора используя лемму №3, чтобы найти медиану а затем использовать лемму №6 для сортировки. Для набора где все элементы равны медиане, не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. [math]Return[/math].
2. От [math]u = 1[/math] до [math]k[/math]
   1. Упаковать [math]a^{(u)}_{i}[/math]-ый в часть из [math]1/k[/math]-ых номеров контейнеров, где [math]a^{(u)}_{i}[/math] содержит несколько непрерывных блоков, которые состоят из [math]1/k[/math]-ых битов [math]a_{i}[/math] и у которого текущий блок это самый крупный блок.
   2. Вызвать Sort([math]k \log\log n[/math], [math]level - 1[/math], [math]a^{(u)}_{0}[/math], [math]a^{(u)}_{1}[/math], [math]\ldots[/math], [math]a^{(u)}_{t}[/math]). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к которому набору это число относится, уже отправлен назад к месту где число находится во входных данных. Число имеющее наибольшее число бит в [math]a_{i}[/math], показывающее на ткущий блок в нем, так же отправлено назад к [math]a_{i}[/math].
   3. Отправить [math]a_{i}-ые к их наборам, используя \lt b\gt лемму №6\lt /b\gt .[/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]\ldots[/math], [math]a_{n - 1}[/math]);

от 1 до 5

1. Поместить [math]a_{i}[/math] в соответствующий набор с помощью bucket sort потому, что наборов около [math]\sqrt{n}[/math]
2. Для каждого набора [math]S = [/math]{[math]a_{i_{0}}, a_{i_{1}}, \ldots, 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}}, \ldots, a_{i_{t}}[/math])

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

Лемма №3

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

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

Так как возможно делать попарное сравнение [math]g[/math] чисел в одном контейнере с [math]g[/math] числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, [math]\ldots[/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] контейнеров и затем продолжим рекурсию.

Лемма №4

Если [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](\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]g = O( \log n)[/math] сортировка [math]O(n)[/math] чисел в [math]n/g[/math] контейнеров произойдет за время [math]O((n/g) \log\log n)[/math], с использованием O(n/g) места. Выгода очевидна.

Лемма №5

Если принять, что каждый контейнер содержит [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]-ом контейнере для маркеров.

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

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

Лемма №6

предположим, что каждый контейнер содержит [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]\log m \log\log n[/math] бит всего [math]\log m[/math] бит используется для хранения упакованных чисел. Так же как в леммах №4, №5 сортируем контейнеры упакованных маркеров с помощью 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]\log m \log\log n[/math] и только [math]\log m[/math] бит используется для упаковки [math]g \le \log n[/math] чисел в один контейнер, тогда выбор в лемме №3 может быть сделан за время и место [math]O(n/g)[/math], потому, что упаковка в доказатльстве леммы №3 теперь может быть сделана за время [math]O(n/g)[/math].

Литераура

1. Deterministic Sorting in O(n \log\log n) Time and Linear Space. Yijie Han.
2. А. Андерссон. Fast deterministic sorting and searching in linear space. Proc. 1996 IEEE Symp. on Foundations of Computer Science. 135-141(1996)