Цифровая сортировка

Цифровая сортировка — это способ применить идею сортировки подсчетом на большие ключи.

Пусть нам нужно отсортировать большой массив int-ов — скажем, $10^5$ элементов. Мы можем сначала отсортировать его по первым двум байтам (то есть используя $\lfloor x / 2^{16} \rfloor$ как ключ) стабильной сортировкой подсчетом, а затем получившуюся последовательность отсортировать по вторым двум байтам (используя $x \bmod 2^{16}$ как ключ).

Реализация, использующая подсчет через массив векторов:

const int c = (1<<16);

void radix_sort(vector<int> &a) {
    int n = (int) a.size();
    vector<int> b[c];

    for (int i = 0; i < n; i++)
        b[a[i] % c].push_back(a[i]);
    
    int k = 0;
    for (int i = 0; i < c; i++) {
        for (size_t j = 0; j < b[i].size(); j++)
            a[k++] = b[i][j];
        b[i].clear();
    }

    for (int i = 0; i < n; i++)
        b[a[i]/c].push_back(a[i]);
    
    k = 0;
    for (int i = 0; i < c; i++)
        for (size_t j = 0; j < b[i].size(); j++)
            a[k++] = b[i][j];
}

Этот подход можно обобщить на любой тип и размер ключа.