Поразрядная сортировка

На мой взгляд, наилучшими характеристиками обладает так называемая поразрядная сортировка. Сразу же привлекает внимание то, что в ней полностью отсутствуют сравнения, а самое главное – она линейна. Для длинных списков – идеальный вариант. Для массивов... не очень, так как требует дополнительной памяти под "карманы".

Теперь всё объясню в подробностях. Суть поразрядной сортировки в следующем: данные сортируются, как это видно из названия, по разрядам, т. е. числа по цифрам, строки – по символам. Сначала упорядочивается младший разряд, затем второй справа, далее третий и т. д. Для процедуры сортировки нужны карманы. В случае сортировки чисел можно предусмотреть, к примеру, 10 карманов (от 0 до 9). Проходя по списку, будем помещать его элементы в соответствующий карман.

Приведу небольшой пример для целых чисел. На первой итерации (обработка младшего разряда) элементы 74, 586, 123, 896, 12, 32 попадут в карманы 4, 6, 3, 6, 2 и 2 соответственно. Карманы "склеиваются", получаем 12, 32, 123, 74, 586, 896. Затем полученный список сортируем по второму справа разряду, при этом наши элементы попадают в карманы 1, 3, 2, 7, 8, 9. При склеивании получаем список 12, 123, 32, 74, 586, 896. Ну и по аналогии сортируем старший разряд (учитывая, что у двузначных чисел он равен нулю). Получаем в результате список 12, 32, 74, 123, 586, 896. Сортировка закончена.

Теперь рассмотрим вопрос реализации данного алгоритма.