Голубиная СортировкаPigeonhole Sort

Пусть все значения массива лежат в диапазоне [min, max], k = max - min + 1. Заводится k "ячеек" (списков), проиндексированных значением минус min. Один линейный проход по массиву кладёт каждый элемент a[i] в ячейку с индексом a[i] - min, добавляя его в конец списка этой ячейки (это и обеспечивает стабильность — элементы с одинаковым значением остаются в исходном относительном порядке). Второй линейный проход по ячейкам в порядке возрастания индекса выписывает их содержимое подряд — результат отсортирован, потому что ячейки уже расположены по возрастанию значения, а внутри каждой ячейки все элементы равны.Let all array values lie in [min, max], k = max - min + 1. k "holes" (lists) are set up, indexed by value minus min. A single linear pass over the array places each element a[i] into the hole at index a[i] - min, appending it to that hole's list (this is what guarantees stability — elements with equal values keep their original relative order). A second linear pass over the holes in increasing index order writes their contents out in sequence — the result is sorted because the holes are already arranged by increasing value, and every element within one hole is equal.

std::vector<int> pigeonhole_sort(const std::vector<int>& a) {
    if (a.empty()) return {};
    int mn = *std::min_element(a.begin(), a.end());
    int mx = *std::max_element(a.begin(), a.end());
    int k = mx - mn + 1;

    std::vector<std::vector<int>> holes(k);
    for (int v : a) holes[v - mn].push_back(v);  // push_back сохраняет исходный порядок// push_back preserves original order

    std::vector<int> result;
    result.reserve(a.size());
    for (auto& hole : holes)
        for (int v : hole) result.push_back(v);
    return result;
}

Верхний ряд — исходный массив. Ячейки — по одной на каждое возможное значение в диапазоне [min, max]. Нижний ряд — результат, заполняемый по мере обхода ячеек по порядку.The top row is the input array. The holes are one per possible value in [min, max]. The bottom row is the output, filled while sweeping the holes in order.

Асимптотика та же — O(n + k) по времени и памяти. Разница чисто в реализации: counting sort хранит только числа (счётчики) и восстанавливает результат через префиксные суммы, что даёт компактную структуру данных (массив int) и хорошую кэш-локальность. Pigeonhole sort хранит в каждой ячейке сам список элементов (не просто счётчик), что удобно, когда сортируются не голые числа, а записи с полезной нагрузкой (a[i] — это ключ, привязанный к какому-то объекту) — не нужно восстанавливать исходные объекты по счётчику, они уже физически лежат в нужной ячейке. Ценой этого — больше накладных расходов на память (указатели/списки вместо плоского массива счётчиков).The asymptotics are the same — O(n + k) time and memory. The difference is purely in implementation: counting sort stores only numbers (counters) and reconstructs the result via prefix sums, giving a compact data structure (an int array) and good cache locality. Pigeonhole sort stores the actual list of elements in each hole (not just a counter), which is convenient when sorting not bare numbers but records with a payload (a[i] is a key attached to some object) — there's no need to reconstruct the original objects from a counter, they're already physically sitting in the right hole. The cost is more memory overhead (pointers/lists instead of a flat counter array).

Из-за этого pigeonhole sort почти всегда описывается как учебный, а не производственный алгоритм — на практике для случая "ключ с полезной нагрузкой" обычно используют counting sort с массивом индексов вместо самих объектов (тот же эффект, компактнее по памяти).Because of this, pigeonhole sort is almost always described as a teaching algorithm rather than a production one — in practice, the "key with a payload" case is usually handled with counting sort using an array of indices instead of the objects themselves (the same effect, more compact in memory).