Изменения

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

{{Лемма

|id=lemma1.

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

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

{{Лемма

|id=lemma2.

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

}}

{{Лемма

|id=lemma3.

Так как мы можем делать попарное сравнение <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> контейнеров и затем продолжим рекурсию.

}}

{{Лемма

|id=lemma4.

Заметим, что когда <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=lemma6.