Изменения
Нет описания правки
Изначально запускаем функцию так <math>\mathrm{radixSort(A, 0, A.length - 1, 1)}</math>
'''function''' radixSort(int[] A, int l, int r, int d):
'''if''' d > m '''or''' l >= r
'''return'''
Если количество разрядов {{---}} константа, а <tex> k = O(n) </tex>, то сложность цифровой сортировки составляет <tex> O(n) </tex>, то есть она линейно зависит от количества сортируемых чисел.
===Сложность MSD-сортировки===
Пусть значения разрядов меньше <tex>b</tex>, а количество разрядов {{---}} <tex>k</tex>. При сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной <tex>O(n \times knk)</tex>, причем это время нельзя улучшить. Хорошим случаем для данной сортировки будем будет массив, при котором на каждом шаге каждая корзина будет делиться на <tex>b </tex> частей. Как только размер корзины станет равен <tex>1</tex>, то больше сортировка не будет перестанет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет <math>\Omega(n \times log_b{n})</math>. Это хорошо тем, что не зависит от числа разрядов.
Существует так же модификация MSD-сортировки, при которой рекурсивный процесс останавливается при небольших размерах текущего кармана , и вызывается более быстрая сортировка основанная на сравнениях (например, сортировка вставками).
== См. также ==
