81
правка
Изменения
Нет описания правки
<tex>kloglogn</tex> это неконсервативное преимущество, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, <tex>level</tex> это уровень рекурсии.
1) <tex>if level == 1</tex> тогда изучить размер набора. Еслиразмер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе разделить этот набор в <= 3 набора используя лемму три, чтобы найти медиану а затем использовать лемму 6 для сортировки. Для набора где все элементы равны медиане, не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. <tex>Return</tex>. 2) От <tex>u = 1</tex> до <tex>k</tex> 2.1) Упаковать <tex>a^{(u)}_{i}</tex>-ый в часть из <tex>1/k</tex>-ых номеров контейнеров, где <tex>a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex>1/k</tex>-ых битов <tex>a_{i}</tex> и у которого текущий блок это самый крупный блок. 2.2) Вызвать Sort(<tex>kloglogn</tex>, <tex>level - 1</tex>, <tex>a^{(u)}_{0}</tex>, <tex>a^{(u)}_{1}</tex>, ..., <tex>a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к которому набору это число относится, уже отправлен назад к месту где число находится во входных данных. Число имеющее наибольшее число бит в <tex>a_{i}</tex>, показывающее на ткущий блок в нем, так же отправлено назад к <tex>a_{i}</tex>. 2.3) Отправить <tex>a_{i}-ые к их наборам, используя лемму шесть.</tex> end. Algorithm IterateSortCall Sort(<tex>kloglogn</tex>, <tex>log_{k}((logn)/4)</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, ..., <tex>a_{n - 1}</tex>); от 1 до 5 Поместить <tex>a_{i}</tex> в соответствующий набор с помощью bucket sort потому, что наборов около <tex>\sqrt{n}</tex> Для каждого набора <tex>S = {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>)
