от 1 до 5
начало # Поместить <tex>a_{i}</tex> в соответствующий набор с помощью bucket sort потому, что наборов около <tex>\sqrt{n}</tex> # Для каждого набора <tex>S = </tex>{<tex>a_{i_{0}}, a_{i_{1}}, ..., a_{i_{t}}</tex>}, если <tex>t > sqrt{n}</tex>, вызвать Sort(<tex>k \log\log n</tex>, <tex>\log_{k}((\log n)/4)</tex>, <tex>a_{i_{0}}, a_{i_{1}}, ..., a_{i_{t}}</tex>) конец
Время работы алгоритма <tex>O(n \log\log n/ \log k)</tex>, что доказывает лемму 2.
