Поразрядная сортировка. Алгоритм и его характеристики

Гоша: Теперь я специалист по сортировкам. Сейчас подумаю и выберу самые подходящие алгоритмы для решения обеих задач.

Тимофей: Ты думаешь, что знаешь все методы сортировки?

Гоша: А разве нет?

Тимофей: А ты слышал, что бывает поразрядная сортировка (англ. radix sort)?

Гоша: Да, слышал. Правда один раз — только что. Расскажи про неё, пожалуйста.

Тимофей: Изначально алгоритм поразрядной сортировки был предназначен для сортировки целых чисел. Но так как в памяти компьютера вся информация записывается в виде целых чисел, алгоритм пригоден для сортировки любых объектов, запись которых можно разделить на разряды. Разряды должны содержать сравнимые значения.

Например, этим алгоритмом можно сортировать строки. И вообще любые значения в памяти компьютера, представленные в виде набора байтов.

Так как алгоритм применяют для сортировки разных данных, назовём сортируемые объекты ключами. Например, ключом может быть число или строка.

До сортировки нужно знать два параметра: $k$ и $m$, где:

Например, при сортировке слов, записанных русскими буквами, $m=33$. Ведь в русском алфавите 33 буквы. Если в самом длинном из сортируемых слов 10 букв, то $k=10$.

При сортировке шестнадцатеричных чисел $m=16$, если в качестве разряда брать цифру. Если же использовать побайтовое деление, то $m=256$.

Параметры $k$ и $m$ нельзя изменять в процессе работы алгоритма.

Отсортируем множество трёхзначных чисел.
Разобьём ключ на фрагменты и представим его в виде массива.

Каждый ключ должен иметь равное число фрагментов.

Например, ключ 375 можно разбить на 3 фрагмента [3, 7, 5], ключ 5 — тоже: [0, 0, 5].

Отсортируем массив S = [154, 267, 324, 615, 345, 994, 24].

Разобьём ключ на 3 фрагмента.

При размере исходного массива $n$, а вспомогательного — 10, потребуется провести всего три сортировки подсчётом. Сложность алгоритма $3O(n)$, то есть $O(n)$.

Гоша: Круто! И кто придумал эту сортировку?

Тимофей: Гарольд Сьюард, ещё в 1954 году.

Гоша: А, ну если бы ни Гарольд, я бы сам придумал! Это ему повезло, что он родился раньше.

Тимофей: Ну раз ты такой умный, расскажи, какими алгоритмами будем решать задачи Кондратия? Кстати, уточнили требования по обеим.

Сортировать жителей по количеству нарушений нужно за $O(n)$. Алгоритм должен работать очень быстро. Количество жителей Трешландии всё увеличивается. Особенно много иммигрантов прибыло из Пчеляндии после налёта стаи синичек. При этом алгоритм должен быть устойчивым.

Метод сортировки населённых пунктов по «треш-индексу» должен работать с одинаковой асимптотикой на любых входных данных.

Гоша: Я знаю! Для обеих задач возьмём сортировку подсчётом! Или поразрядную!

Тимофей: Для задачи с городами эти варианты не подойдут. Значение «треш-индекса» может быть произвольным. Мы заранее не знаем даже количество знаков в максимальном индексе.

Гоша: Тогда для этой задачи применим сортировку слиянием. Ведь важно, чтобы в худшем случае время работы алгоритма не отличалось от произвольного случая.

Тимофей: Да, согласен с твоим выбором.

Решите задачи M, N: https://contest.yandex.ru/contest/18899/problems/M/