Изменения

Будем считать, что у всех элементов одинаковое число разрядов. Если это не так, то положим на более старших разрядах элементы с самым маленьким значением — для чисел это <tex>0</tex>. Сначала исходный массив делится на <tex>k</tex> частей, где <tex>k</tex> — основание, выбранное для представления сортируемых объектов. Эти части принято называть "корзинами" или "карманами". В первую корзину попадают элементы, у которых старший разряд с номером <tex>d = 0</tex> имеет значение <tex>0</tex>. Во вторую корзину попадают элементы, у которых старший разряд с номером <tex>d = 0</tex> имеет значение <tex>1</tex> и так далее. Затем элементы, попавшие в разные корзины, подвергаются рекурсивному разделению по следующему разряду с номером <tex>d = 1</tex>. Рекурсивный процесс разделения продолжается, пока не будут перебраны все разряды сортируемых объектов и пока размер корзины больше единицы. (то То есть останавливаемся когда <tex>d > m</tex> или <tex>l \geq geqslant r</tex>, где m — максимальное число разрядов в сортируемых объектах, <tex>l</tex>, <tex>r</tex> — левая и правая границы отрезка массива <tex>A</tex>).

Изначально запускаем функцию так <texmath>\mathrm{radixSort(A, 10, A.length- 1, 1)}</texmath>

 ===Сложность MSD-сортировки оценивается величиной ===Пусть значения разрядов меньше <tex>b</tex>, а количество разрядов {{---}} <tex>O(n \log_k n)k</tex>. При больших k величина сортировке массива из одинаковых элементов MSD-сортировкой на каждом шаге все элементы будут находится в неубывающей по размеру корзине, а так как цикл идет по всем элементам массива, то получим, что время работы MSD-сортировки оценивается величиной <tex>O(n \log_k ntimes k)</tex> становится малой и сложность становится линейной функцией , причем это время нельзя улучшить. Хорошим случаем для данной сортировки будем массив, при котором на каждом шаге каждая корзина будет делиться на b частей. Как только размер корзины станет равен 1, то больше сортировка не будет рекурсивно запускаться в этой корзине. Таким образом, асимптотика будет <texmath>O\Omega(n\times log_b{n})</texmath> . Это хорошо тем, что не зависит от числа разрядов.