Сортировка Хана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(nlog(log n))</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
+
'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(nloglog n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
  
 
Данная статья писалась на основе брошюры Хана, посвященной этой сортировке. Изложение материала в данной статье идет примерно в том же порядке, в каком она предоставлена в работе Хана.
 
Данная статья писалась на основе брошюры Хана, посвященной этой сортировке. Изложение материала в данной статье идет примерно в том же порядке, в каком она предоставлена в работе Хана.
Строка 18: Строка 18:
 
|id=def2.  
 
|id=def2.  
 
|definition=
 
|definition=
Алгоритм сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> называется консервативным, если длина контейнера (число бит в контейнере), является <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм не консервативный.
+
Алгоритм сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> называется консервативным, если длина контейнера (число бит в контейнере), является <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм неконсервативный.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|id=def3.  
 
|id=def3.  
 
|definition=
 
|definition=
Если мы сортируем целые числа из множества {0, 1, ..., <tex>m</tex> - 1} с длиной контейнера <tex>klog(m + n)</tex> с <tex>k</tex> >= 1, тогда мы сортируем с не консервативным преимуществом <tex>k</tex>.
+
Если мы сортируем целые числа из множества {0, 1, ..., <tex>m</tex> - 1} с длиной контейнера <tex>klog(m + n)</tex> с <tex>k</tex> >= 1, тогда мы сортируем с неконсервативным преимуществом <tex>k</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 70: Строка 70:
 
|id=lemma2.  
 
|id=lemma2.  
 
|statement=
 
|statement=
<tex>n</tex> целых чисел можно отсортировать в <tex>\sqrt{n}</tex> наборов <tex>S_{1}</tex>, <tex>S_{2}</tex>, ..., <tex>S_{\sqrt{n}}</tex> таким образом, что в каждом наборе <tex>\sqrt{n}</tex> чисел и <tex>S_{i}</tex> < <tex>S_{j}</tex> при <tex>i</tex> < <tex>j</tex>, за время <tex>O(nlog(logn)/logk)</tex> и место <tex>O(n)</tex> с не консервативным преимуществом <tex>klog(logn)</tex>
+
<tex>n</tex> целых чисел можно отсортировать в <tex>\sqrt{n}</tex> наборов <tex>S_{1}</tex>, <tex>S_{2}</tex>, ..., <tex>S_{\sqrt{n}}</tex> таким образом, что в каждом наборе <tex>\sqrt{n}</tex> чисел и <tex>S_{i}</tex> < <tex>S_{j}</tex> при <tex>i</tex> < <tex>j</tex>, за время <tex>O(nloglogn/logk)</tex> и место <tex>O(n)</tex> с не консервативным преимуществом <tex>kloglogn</tex>
 
|proof=
 
|proof=
 +
Доказательство данной леммы будет приведено далее в тексте статьи.
 
}}
 
}}
 
{{Лемма
 
{{Лемма
Строка 90: Строка 91:
 
}}
 
}}
  
Заметим, что когда <tex>g = O(logn)</tex> мы сортируем <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров за время <tex>O((n/g)log(logn))</tex>, с использованием O(n/g) места. Выгода очевидна.
+
Заметим, что когда <tex>g = O(logn)</tex> мы сортируем <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров за время <tex>O((n/g)loglogn)</tex>, с использованием O(n/g) места. Выгода очевидна.
  
 
{{Лемма
 
{{Лемма
 
|id=lemma5.
 
|id=lemma5.
 
|statement=
 
|statement=
Если принять, что каждый контейнер содержит <tex>logm > logn</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>(logm)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(logn)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O((nlog(logn))/g)</tex> с использованием <tex>O(n/g)</tex> места.
+
Если принять, что каждый контейнер содержит <tex>logm > logn</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>(logm)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(logn)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O((nloglogn)/g)</tex> с использованием <tex>O(n/g)</tex> места.
 
(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.
 
(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.
 
|proof=
 
|proof=
Строка 112: Строка 113:
  
 
Заметим, что если длина контейнера <tex>logmloglogn</tex> и только <tex>logm</tex> бит используется для упаковки <tex>g <= logn</tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)</tex>.
 
Заметим, что если длина контейнера <tex>logmloglogn</tex> и только <tex>logm</tex> бит используется для упаковки <tex>g <= logn</tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)</tex>.
 +
 +
==Сортировка <tex>n</tex> целых чисел в <tex>\sqrt{n}</tex> наборов==
 +
Постановка задачи и решение некоторых проблем:
 +
 +
Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества {0, 1, ..., <tex>m</tex> - 1} в <tex>\sqrt{n}</tex> наборов как во второй лемме. Мы предполагаем, что в каждом контейнере <tex>kloglognlogm</tex> бит и хранит число в <tex>logm</tex> бит. Поэтому неконсервативное преимущество <tex>kloglogn</tex>. Мы так же предполагаем, что <tex>logm >= lognloglogn</tex>. Иначе мы можем использовать radix sort для сортировки за время <tex>O(nloglogn)</tex> и линейную память. Мы делим <tex>logm</tex> бит, используемых для представления каждого числа, в <tex>logn</tex> блоков. Таким образом каждый блок содержит как минимум <tex>loglogn</tex> бит. <tex>i</tex>-ый блок содержит с <tex>ilogm/logn</tex>-ого по <tex>((i + 1)logm/logn - 1)</tex>-ый биты. Биты считаются с наименьшего бита начиная с нуля. Теперь у нас имеется <tex>2logn</tex>-уровневый алгоритм, который работает следующим образом:

Версия 01:36, 12 июня 2012

Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью [math]O(nloglog 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]klog(m + n)[/math] с [math]k[/math] >= 1, тогда мы сортируем с неконсервативным преимуществом [math]k[/math].


Определение:
Для множества [math]S[/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 = 2logn[/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]logm[/math] бит. Мы рассматриваем, что в каждом числе есть [math]h[/math] сегментов, в каждом из которых [math]log(m/h)[/math] бит. Теперь мы применяем хэширование ко всем сегментам и получаем [math]2hlogn[/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]logm[/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(nloglogn/logk)[/math] и место [math]O(n)[/math] с не консервативным преимуществом [math]kloglogn[/math]
Доказательство:
[math]\triangleright[/math]
Доказательство данной леммы будет приведено далее в тексте статьи.
[math]\triangleleft[/math]
Лемма:
Выбор [math]s[/math]-ого наибольшего числа среди [math]n[/math] чисел упакованных в [math]n/g[/math] контейнеров может быть сделана за [math]O(nlogg/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](logn)/2[/math] бит, упакованы в один контейнер, тогда [math]n[/math] чисел в [math]n/g[/math] контейнерах могут быть отсортированы за время [math]O((n/g)logg)[/math], с использованием [math]O(n/g)[/math] места.
Доказательство:
[math]\triangleright[/math]

Так как используется только [math](logn)/2[/math] бит в каждом контейнере для хранения [math]g[/math] чисел, мы можем использовать bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает [math]O(n/g)[/math] времени и места. Потому, что мы используем [math](logn)/2[/math] бит на контейнер нам понадобится [math]\sqrt {n}[/math] шаблонов для всех контейнеров. Затем поместим [math]g \lt (logn)/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(glogg)[/math], с использованием [math]O(g)[/math] места. Для всех групп это занимает время [math]O((n/g)logg)[/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(logn)[/math] мы сортируем [math]O(n)[/math] чисел в [math]n/g[/math] контейнеров за время [math]O((n/g)loglogn)[/math], с использованием O(n/g) места. Выгода очевидна.

Лемма:
Если принять, что каждый контейнер содержит [math]logm \gt logn[/math] бит, и [math]g[/math] чисел, в каждом из которых [math](logm)/g[/math] бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий [math](logn)/(2g)[/math] бит, и [math]g[/math] маркеров упакованы в один контейнер таким же образом[math]^*[/math], что и числа, тогда [math]n[/math] чисел в [math]n/g[/math] контейнерах могут быть отсортированы по их маркерам за время [math]O((nloglogn)/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](logn)/2[/math] бит. Сортировка сгруппирует контейнеры для чисел как в четвертой лемме. Мы можем переместить каждую группу контейнеров для чисел.
[math]\triangleleft[/math]

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

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

Лемма:
предположим, что каждый контейнер содержит [math]logmloglogn \gt logn[/math] бит, что [math]g[/math] чисел, в каждом из которых [math](logm)/g[/math] бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий [math](logn)/(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]logmloglogn[/math] бит всего [math]logm[/math] бит используется для хранения упакованных чисел. Так же как в леммах четыре и пять мы сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел мы помещаем [math]gloglogn[/math] вместо [math]g[/math] контейнеров чисел в одну группу. Для транспозиции чисел в группе содержащей [math]gloglogn[/math] контейнеров мы сначала упаковываем [math]gloglogn[/math] контейнеров в [math]g[/math] контейнеров упаковывая [math]loglogn[/math] контейнеров в один. Далее мы делаем транспозицию над [math]g[/math] контейнерами. Таким образом перемещение занимает всего [math]O(gloglogn)[/math] времени для каждой группы и [math]O(n/g)[/math] времени для всех чисел. После завершения транспозиции, мы далее распаковываем [math]g[/math] контейнеров в [math]gloglogn[/math] контейнеров.
[math]\triangleleft[/math]

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

Сортировка [math]n[/math] целых чисел в [math]\sqrt{n}[/math] наборов

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

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