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

Сортировка подсчётом упирается в размер диапазона: при значениях до $10^9$ массив счётчиков не поместится в память. Но у чисел есть структура, которой можно воспользоваться, — они состоят из разрядов, и каждый разряд принимает мало значений.

Идея

Отсортируем числа по последнему разряду. Потом — по предпоследнему. Потом по следующему, и так до старшего.

Пусть числа двузначные: 52 13 47 11 43.

Сортируем по единицам: 11 52 13 43 47. По десяткам: 11 13 43 47 52. Готово.

Почему получилось? После сортировки по десяткам числа с разными десятками стоят верно. А числа с одинаковыми десятками — 43 и 47 — сохранили тот порядок, который у них был после сортировки по единицам, то есть верный.

Устойчивость здесь не украшение, а условие

Весь алгоритм держится на том, что сортировка по очередному разряду не разрушает порядок, наведённый предыдущими. Это и есть устойчивость.

Возьмите неустойчивую сортировку по десяткам — и 43 с 47 могут поменяться местами. Никакая ошибка при этом не проявится сразу: массив будет отсортирован по десяткам, просто внутри группы порядок случайный, и итог окажется неверным.

Внутренней сортировкой обычно берут подсчёт: разряд принимает мало значений, счётчиков нужно немного, и устойчивость получается естественно, если выписывать элементы группами слева направо.

Основание

Разряды не обязаны быть десятичными. Удобнее брать основание 256 и считать разрядом один байт: тогда 32-битное число разбирается за 4 прохода, 64-битное — за 8, а счётчиков всегда 256.

// Числа неотрицательные, 32 бита, четыре прохода по байтам.
void radix_sort(vector<unsigned>& a) {
    vector<unsigned> buffer(a.size());
    for (int shift = 0; shift < 32; shift += 8) {
        int count[256] = {0};
        for (unsigned value : a) count[(value >> shift) & 255]++;
        // Префиксные суммы: где начинается группа каждого байта.
        int pos[256];
        pos[0] = 0;
        for (int i = 1; i < 256; i++) pos[i] = pos[i - 1] + count[i - 1];
        // Проход слева направо — отсюда и устойчивость.
        for (unsigned value : a) buffer[pos[(value >> shift) & 255]++] = value;
        a.swap(buffer);
    }
}

Обратите внимание на префиксные суммы: они говорят, с какой позиции начинается группа каждого значения байта. Дальше элементы раскладываются одним проходом, и порядок внутри группы сохраняется, потому что проход идёт слева направо.

Сколько это стоит

Проходов $k$ (число разрядов), каждый стоит $O(n + b)$, где $b$ — основание. Итого $O(k(n + b))$.

Для 32-битных чисел основанием 256 это $4(n + 256)$ — то есть примерно $4n$ при больших $n$. Сравните с $n \log_2 n$: при $n = 10^7$ логарифм равен 23, и разница получается почти шестикратной.

Правда, у поразрядной большая константа на проход и нужна дополнительная память под буфер. Реальный выигрыш начинается на миллионах элементов; на сотне тысяч sort обычно быстрее.

	Поразрядная	Сортировка сравнениями
Время	$O(k \cdot n)$	$O(n \log n)$
Память	$O(n + b)$	$O(1)$ или $O(n)$
Что нужно от данных	ключи фиксированной длины	только сравнение
Устойчивость	да	зависит

Отрицательные числа и не только

Код выше сортирует беззнаковые. Со знаковыми есть тонкость: в двоичном представлении отрицательные числа начинаются с единичного старшего бита и при сравнении байтов оказываются «больше» положительных.

Лечится сдвигом: прибавить ко всем числам $2^{31}$ (то есть инвертировать старший бит), отсортировать как беззнаковые, вычесть обратно. Тот же приём, что и сдвиг на минимум в сортировке подсчётом.

Строки сортируют похоже, но с другого конца — начиная со старшего разряда, то есть с первого символа, и рекурсивно разбирая группы. Такой вариант называется MSD, и он ближе к быстрой сортировке, чем к подсчёту.

Когда вспоминать

Признаки задачи, где поразрядная уместна: элементов миллионы, ключи — целые числа фиксированной длины, лимит времени тесный, а обычная сортировка в него не укладывается. Во всех остальных случаях sort проще и быстрее.