Цифровая сортировка

Цифровая сортировка — алгоритм сортировки за линейное время.

Алгоритм

При цифровой сортировке данные разбиваются на "разряды", после этого данные сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Для чисел наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.

Сложность

Пусть [math]m[/math] - количество разрядов, n - количество входных данных, T(n) - сложность устойчивой сортировки, тогда сложность цифровой сортировки - [math]О(m*T(n))[/math]. При использовании сортировки подсчетом получаем линейную зависимость.

Псевдокод

 Radix_sort
 for i = 1 to m
    do устойчивая сортировка массива по i-ому разряду