Изменения

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

Номер один.

{{Лемма

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

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

Номер два.

{{Лемма

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

}}

Номер три.

{{Лемма

Так как мы можем делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, мы можем упаковать медианы из первого, второго, ..., <tex>g</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом набор <tex>S</tex> из медиан теперь содержится в <tex>n/(5g)</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex> уберем хотя бы <tex>n/4</tex> чисел среди <tex>n</tex>. Затем упакуем оставшиеся из <tex>n/g</tex> контейнеров в <tex>3n/4g</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>-уровневый алгоритм, который работает следующим образом: