81
правка
Изменения
Нет описания правки
от 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>kloglogn</tex>, <tex>log_{k}((logn)/4)</tex>, <tex>a_{i_{0}}, a_{i_{1}}, ..., a_{i_{t}}</tex>) конец Время работы алгоритма <tex>O(nloglogn/logk)</tex>, что доказывает лемму 2. ==Собственно сортировка с использованием <tex>O(nloglogn) времени и памяти</tex>==
