How it works?

Поразрядная сортировка (Radix Sort) обрабатывает по одной позиции цифры за раз, от наименее значимой (единицы) до наиболее значимой. На каждом проходе используется стабильная сортировка, чтобы результаты предыдущих проходов сохранялись.

Пошаговый процесс:

1. Сортировка по разряду единиц с использованием стабильной сортировки подсчетом.
2. Сортировка по разряду десятков, сохраняя предыдущий порядок при совпадении значений.
3. Продолжение процесса для сотен, тысяч и так далее, пока не будет обработан разряд самого большого числа.

Пример на [170, 45, 75, 90, 2, 802, 24, 66]:

• По разряду единиц: [170, 90, 2, 802, 24, 45, 75, 66]
• По разряду десятков: [2, 802, 24, 45, 66, 170, 75, 90]
• По разряду сотен: [2, 24, 45, 66, 75, 90, 170, 802]

После обработки последнего разряда массив полностью отсортирован. Магия заключается в том, что стабильность сохраняет порядок младших разрядов, пока старшие разряды вступают в силу.