Изменения

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

Набор <tex>S1</tex> < <tex>S2</tex> если max(<tex>S1</tex>) <tex>\le </tex> min(<tex>S2</tex>)

Даны целые числа <tex>b</tex> <tex> \ge </tex> <tex>s</tex> <tex> \ge </tex> 0 и <tex>T</tex> является подмножеством {0, ..., <tex>2^b</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>if level == 1</tex> тогда изучить размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе разделить этот набор в <tex>\le </tex> 3 набора используя лемму три, чтобы найти медиану а затем использовать лемму 6 для сортировки. Для набора где все элементы равны медиане, не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. <tex>Return</tex>.