Сортування за розрядами
Матеріал з Вікіпедії — вільної енциклопедії.
Сортування за розрядами (англ. Radix sort) — швидкий стабільний алгоритм впорядкування даних. Застосовується для впорядкування елементів, що є ланцюжками над будь-яким скінченним алфавітом (напр. рядки, або цілі числа). В якості допоміжного використовує будь-який інший стабільний алгоритм сортування.
Алгоритм застосовувався для впорядкування перфокарт.
[ред.] Ідея алгоритму
Ідея полягає в тому, щоб спочатку впорядкувати всі елементи за молодшим розрядом, потім стабільно впорядкувати за другим розрядом, потім за третім і так далі аж до найстаршого. Оскільки, припускається, що кожен разряд приймає значення з невеликого діапазону, то кожен цикл впорядкування можна виконувати швидко і з малими затратами пам'яті.
[ред.] Приклад роботи
В прикладі показано, як впорядковувати таким алгоритмом масив трицифрових чисел:
572 572 523 266
266 523 349 349
783 --> 783 --> 266 --> 523
523 266 572 572
349 349 783 783
^ ^ ^
[ред.] Аналіз
Час роботи кожного циклу сортування залежить від того алгоритму, що використовується в якості допоміжного. Найчастіше використовують сортування підрахунком, що пряцює за час 
(де N — кількість елементів в масиві; K — кількість символів у алфавіті, якщо впорядковуються десяткові числа, то K = 10) і використовує додатково пам'яті. Всього здійснюється стільки циклів впорядкування, скільки розрядів у максимальному єлементі.
Загальна складність роботи алгоритму з використанням сортування підрахунком є 
(D — кількість розрядів). Якщо впорядковувати цим алгоритмом цілі числа, то складність буде 
, де M — найбільший елемент масиву.
