38
правок
Изменения
м
Нет описания правки
}}
{{ Определение | definition =
Если сортируются целые числа из множества <tex>\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\geqslant1</tex> 1, тогда сортировка происходит с '''неконсервативным преимуществом''' <tex>k</tex>.
}}
{{ Определение | definition =
Пример:
<tex>a_{1}</tex> = 3, <tex>a_{2}</tex> = 5, <tex>a_{3}</tex> = 7, <tex>a_{4}</tex> = 10, S = <tex>\{1, 4, 6, 8, 9, 13, 14\}</tex>.
Делим числа на 2 сегмента. Для <tex>a_{1}</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2}</tex> {{---}} верхний 1, нижний 1; <tex>a_{3}</tex> {{---}} верхний 1, нижний 3; <tex>a_{4}</tex> {{---}} верхний 2, нижний 2. Для элементов из S получим: для 1 нижний 1, так как он выделяется из нижнего сегмента <tex>a_{1}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.
==Сортировка с использованием O(n log log n) времени и памяти==
Для сортировки <tex>n</tex> целых чисел в диапазоне {<tex>{0, 1, \ldots, m - 1}</tex>} предполагается, что в нашем консервативном алгоритме используется контейнер длины <tex>O(\log (m + n))</tex>. Далее везде считается, что все числа упакованы в контейнеры одинаковой длины.
