81
правка
Изменения
Нет описания правки
Так как нам не надо полностью сортировать <tex>q</tex> чисел и <tex>q = p^2</tex>, есть возможность использовать лемму 2 для сортировки. Для этого нам надо неконсервативное преимущество которое мы получим ниже. Для этого используем линейную технику многократного деления (multi-dividing technique) чтобы добиться этого.
Для этого воспользуемся signature sorting. Адаптируем этот алгоритм для нас. Предположим у нас есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, ..., a_{p}</tex>, и мы хотим использовать числа в <tex>T</tex> для разделения <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, ..., b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, ..., S_{p}</tex> что <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < ... < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами. Пусть <tex>h = logn/(clogp)</tex> для константы <tex>c > 1</tex>. <tex>h/loglognlogp</tex> битные числа могут быть хранены в одном контейнере, так что одно слово хранит <tex>(logn)/(cloglogn)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины <tex>h/loglogn</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки мы хэштруем числа в этих контейнерах (<tex>a_{i}</tex>-ом и <tex>b_{i}</tex>-ом) чтобы получить <tex>h/loglogn</tex> хэшированных значений в одном контейнере. Чтобы получить значения сразу, при вычислении хэш значений сегменты не влияют друг на друга, мы можем даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хэш значения считаются за константное время. Затем, посчитав значения мы объединяем два контейнера в один. Пусть <tex>a'_{i}</tex> хэш контейнер для <tex>a_{i}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хэш значения имеют <tex>(2logn)/(cloglogn)</tex> бит. Хотя эти значения разделены на сегменты по <tex>h/loglogn</tex> бит в каждом контейнере. Сначала упаковываем все сегменты в <tex>(2logn)/(cloglogn)</tex> бит. Потом рассмотрим каждый хэш контейнер как число и отсортируем эти хэш слова за линейное время. После этой сортировки биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>loglogn/h</tex>. Таким образом мы получили дополнительное мультипликативное преимущество в <tex>h/loglogn</tex> (additional multiplicative advantage).
