Изменения

Для этого воспользуемся 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). После того, как мы повторили вышеописанный процесс <tex>g</tex> раз мы получили неконсервативное преимущество в <tex>(h/loglogn)^g</tex> раз, в то время как мы потратили только <tex>O(gqt)</tex> времени, так как каждое многократное деление делятся за линейное время <tex>O(qt)</tex>. Хэш функция, которую мы используем, находится следующим образом. Мы будем хэшировать сегменты, которые <tex>loglogn/h</tex>-ые, <tex>(loglogn/h)^2</tex>-ые, ... от всего числа. Для сегментов вида <tex>(loglogn/h)^t</tex>, получаем нарезанием всех <tex>p</tex> чисел на <tex>(loglogn/h)^t</tex> сегментов. Рассматривая каждый сегмент как число мы получаем <tex>p(loglogn/h)^t</tex> чисел. Затем получаем одну хэш функцию для этих чисел. Так как <tex>t < logn</tex> то мы получим не более <tex>logn</tex> хэш функций. Рассмотрим сортировку за линейное время о которой было упомянуто ранее.