Суть: разбиваем наши объекты по разрядам и производим сортировку по каждому разряду

[https://www.researchgate.net/figure/Simplistic-illustration-of-the-steps-performed-in-a-radix-sort-In-this-example-the_fig1_291086231 ](https://lh7-us.googleusercontent.com/PbDbb-Vkx7FWd91sGeLe4rCUhkrbtHVIVmkUZcRqGUElkGWw3jZYVBOde3mk3iKlxuB9DDOEaBEvZRht2FDKcCBAeFUX4dJYzZ9cEy_basG56Yan6JwVJ0YupL8uStHphitlcyNrOspQrhTalGU6Mg)

https://www.researchgate.net/figure/Simplistic-illustration-of-the-steps-performed-in-a-radix-sort-In-this-example-the_fig1_291086231

1 шаг – сортировка по значениям крайнего разряда => перезапись шага;

2 шаг и все последующие шаги аналогичны 1 шагу. Делаем эти операции до тех, пока не закончится разряд у самого максимального объекта.

Так как выравнивать сравниваемые записи относительно друг друга можно в разную сторону, на практике существуют два варианта этой сортировки. Для чисел они называются в терминах значимости разрядов числа, и получается так: можно выровнять записи чисел в сторону менее значащих цифр (по правой стороне, со стороны единиц, least significant digit, LSD) или более значащих цифр (по левой стороне, со стороны более значащих разрядов, most significant digit, MSD).

• При LSD сортировке получается порядок, уместный для чисел. Например: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. То есть, здесь значения сначала сортируются по единицам, затем сортируются по десяткам, сохраняя отсортированность на каждом новом шаге.
• При MSD сортировке получается алфавитный порядок, который уместен для сортировки строк текста. Например «b, c, d, e, f, g, h, i, j, ba» отсортируется как «b, ba, c, d, e, f, g, h, i, j». Если MSD применить к числам, приведённым в примере получим последовательность 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Сложность по времени: О(n * k), где

n – количество объектов (для чисел это n-ричная система счисления),

k – количество разрядов максимального объекта.