Изменения

Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам , необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш -функция для хеширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время, без коллизий. Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger и Raman.

Алгоритм: Пусть целое число <tex>b \ge 0</tex> и пусть <tex>U = \{0, \ldots, 2^b - 1\}</tex>. Класс <tex>H_{b,s}</tex> хеш-функций из <tex>U</tex> в <tex>\{0, \ldots, 2^s - 1\}</tex> определен как <tex>H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex>x</tex> из <tex>U</tex>: <tex>h_{a}(x) = (ax</tex> <tex>\bmod</tex> <tex>2^b)</tex> <tex>div</tex> <tex>2^{b - s}</tex>.

Взяв <tex>s = 2 \log n</tex>, получаем хеш-функцию <tex>h_{a}</tex>, которая захеширует <tex>n</tex> чисел из <tex>U</tex> в таблицу размера <tex>O(n^2)</tex> без коллизий. Очевидно, что <tex>h_{a}(x)</tex> может быть посчитана для любого <tex>x</tex> за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, спокойно применяется то можно применить <tex>h_{a}</tex> ко всему контейнеру, а и в результате все хеш-значения для всех чисел в контейере были контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-знчения значения вовлечены только (<tex>\bmod</tex> <tex>2^b</tex>) и (<tex>div</tex> <tex>2^{b - s}</tex>).

Следует отметить, что, несмотря на размер таблицы <tex>O(n^2)</tex>, потребность в памяти не превышает <tex>O(n)</tex> , потому, что хеширование используется только для уменьшения количества бит в числе.