Изменения

# Если сортируются целые числа из множества <tex>{0, 1, ..., <tex>m- 1}</tex> - 1} с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\ge</tex> 1, тогда сортировка происходит с неконсервативным преимуществом <tex>k</tex>.

Даны целые числа <tex>b</tex> <tex>\ge</tex> <tex>s</tex> <tex>\ge</tex> 0 и <tex>T</tex> является подмножеством <tex>{0, ..., <tex>2^b- 1}</tex> - 1}, содержащим <tex>n</tex> элементов, и <tex>t</tex> <tex>\ge</tex> <tex>2^{-s + 1}</tex>С<tex>^k_{n}</tex>. Функция <tex>h_{a}</tex> принадлежащая <tex>H_{b,s}</tex> может быть выбрана за время <tex>O(bn^2)</tex> так, что количество коллизий <tex>coll(h_{a}, T) <tex>\le</tex> t</tex>

Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества <tex>{0, 1, ..., <tex>m- 1}</tex> - 1} в <tex>\sqrt{n}</tex> наборов как во второй лемме. Предполагая, что в каждом контейнере <tex>k \log\log n \log m</tex> бит и хранит число в <tex>\log m</tex> бит. Поэтому неконсервативное преимущество <tex>k \log \log n</tex>. Так же предполагаем, что <tex>\log m \ge \log n \log\log n</tex>. Иначе можно использовать radix sort для сортировки за время <tex>O(n \log\log n)</tex> и линейную память. Делим <tex>\log m</tex> бит, используемых для представления каждого числа, в <tex>\log n</tex> блоков. Таким образом каждый блок содержит как минимум <tex>\log\log n</tex> бит. <tex>i</tex>-ый блок содержит с <tex>i \log m/ \log n</tex>-ого по <tex>((i + 1) \log m/ \log n - 1)</tex>-ый биты. Биты считаются с наименьшего бита начиная с нуля. Теперь у нас имеется <tex>2 \log n</tex>-уровневый алгоритм, который работает следующим образом: