Распределяющая сортировка

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

имеет вид

и их нужно отсортировать в возрастающем лексикографическом порядке, то есть

тогда и только тогда, если для некоторого

имеем

для и . Для простоты будем считать, что , и поэтому имена можно рассматривать как целые, представленные по основанию , так что каждое имя имеет -ичных цифр. Более короткие имена дополняются нулями.

Содержание раздела

---