Голубиная сортировка :: Pigeonhole Sort
Проходим по массиву, если встречается новое число то заводим счётчик (как ключ вспомогательного списка) этого числа. Если число встречается не в первый раз, то просто срабатывает инкремент для этого счётчика.
Отличие от сортировки подсчётом состоит в том, что счётчики для чисел, которые, заводятся только в случае необходимости (для подсчётного метода создаются счётчики для всего возможного диапазона значений массива).
Этот способ иногда альтернативно называется сортировка Дирихле, потому что сам алгоритм является иллюстрацией различных следствий из принципа Дирихле.
| Если N объектов, распределены по M контейнерам, и при этом N > M, то хотя бы в одном контейнере содержится более одного элемента. |
Сортування Діріхле