2.2.2.2 — снимает ограничение counting sort на размер диапазона2.2.2.2 — removes counting sort's constraint on range size
Сортирует не по всему числу сразу, а по разрядам — от младшего к старшему, применяя на каждом проходе стабильную сортировку по разряду. Для фиксированного числа разрядов d время O(d·(n+b)) сводится к O(n), а диапазон значений b может быть сколь угодно большим.Sorts not by the whole number at once, but digit by digit — least to most significant, applying a stable sort at each pass. For a fixed digit count d, the time O(d·(n+b)) reduces to O(n), and the value range b can be arbitrarily large.
Сначала сортируется массив по младшему разряду (стабильно), затем — по следующему, и так далее до старшего разряда. Стабильность на каждом проходе не опциональна, а критична: если сортировка по младшему разряду переставит элементы с одинаковым младшим разрядом произвольно, следующий проход не сможет "унаследовать" уже достигнутый порядок и результат окажется неверным. Основанием разряда обычно берут 10 (десятичные цифры, наглядно для объяснения) или степень двойки вроде 256 (побайтово, эффективно для реализации).First the array is sorted by its least-significant digit (stably), then by the next, and so on up to the most significant. Stability at every pass isn't optional but critical: if sorting by the least-significant digit rearranges elements sharing that digit arbitrarily, the next pass can't "inherit" the ordering already achieved and the result ends up wrong. The digit base is usually 10 (decimal digits, intuitive for explanation) or a power of two like 256 (byte-wise, efficient to implement).
каждый проход опирается на порядок, достигнутый предыдущим — именно поэтому стабильность обязательнаeach pass relies on the order the previous one achieved — exactly why stability is mandatory
// LSD (Least Significant Digit) radix sort по основанию 10// LSD (Least Significant Digit) radix sort, base 10
void radix_sort(std::vector<int>& a) {
int max_val = *std::max_element(a.begin(), a.end());
for (int exp = 1; max_val / exp > 0; exp *= 10) // один проход на разряд// one pass per digit
stable_counting_sort_by_digit(a, exp); // сортировка по (a[i]/exp) % 10// sort by (a[i]/exp) % 10
}Число проходов d равно числу разрядов в максимальном элементе — для 32-битных целых при основании 256 это ровно 4 прохода (по байту), независимо от n. Отсюда время O(d·(n+b)) при фиксированном d вырождается в O(n): рост входа не увеличивает число проходов, только их "толщину".The number of passes d equals the digit count in the largest element — for 32-bit integers with base 256, that's exactly 4 passes (one per byte), independent of n. Hence the time O(d·(n+b)) with fixed d degenerates to O(n): a larger input doesn't increase the number of passes, only their "thickness."
Основание — 10, разряды показаны подписью под каждым баром (текущий разряд — то, что сейчас читается для сортировки). Каждый шаг — один полный стабильный проход по одному разряду; сам механизм "стабильно разложить по цифре 0-9" детально разобран на странице Counting Sort.Base 10, with the digit being sorted by shown as a label under each bar. Each step is one full stable pass over one digit; the mechanism of "stably bucket by digit 0-9" itself is covered in detail on the Counting Sort page.
нажмите «Вперёд» или «Играть», чтобы начатьpress "Forward" or "Play" to begin
Разобранный выше вариант — LSD (Least Significant Digit first): идёт от младшего разряда к старшему, простой и не требует рекурсии. MSD (Most Significant Digit first) идёт в обратную сторону — сортирует по старшему разряду, затем рекурсивно сортирует каждую полученную группу по следующему разряду. MSD не обязан обрабатывать все d разрядов для каждого элемента (короткие группы завершаются раньше), что выгодно для строк переменной длины, но требует рекурсии и more осторожной работы со стабильностью между уровнями.The variant above is LSD (Least Significant Digit first): proceeds from the least to the most significant digit, simple and needs no recursion. MSD (Most Significant Digit first) goes the other way — sorts by the most significant digit, then recursively sorts each resulting group by the next digit. MSD doesn't have to process all d digits for every element (short groups finish early), which is advantageous for variable-length strings, but requires recursion and more careful handling of stability across levels.
Алфавит из 4 символов (A, C, G, T) естественно ложится на radix sort по позициям — каждый символ трактуется как разряд, вся строка сортируется за линейное от суммарной длины входа время.A 4-letter alphabet (A, C, G, T) naturally maps to radix sort by position — each character is treated as a digit, and the whole set sorts in time linear in the total input length.
IPv4-адреса — фиксированной длины 32-битные числа, идеальный кандидат для побайтового radix sort (4 прохода по 8 бит); группировка и сортировка пакетов по адресу использует именно эту фиксированную структуру.IPv4 addresses are fixed-length 32-bit numbers, an ideal candidate for byte-wise radix sort (4 passes of 8 bits each); grouping and sorting packets by address exploits exactly this fixed structure.
Прозрачные объекты сортируются по квантованной глубине перед отрисовкой; GPU-реализации radix sort хорошо параллелизуются, потому что каждый проход по разряду — независимый подсчёт по корзинам, без последовательной зависимости попарного сравнения.Transparent objects are sorted by quantized depth before drawing; GPU radix-sort implementations parallelize well because each digit pass is an independent bucket count, with no sequential dependency from pairwise comparison.
Использование нестабильной сортировки внутри одного прохода молча ломает весь алгоритм — ошибка не проявится ни на каком тесте с "удачными" данными, только на входах, где значения совпадают в младших разрядах.Using an unstable sort within a single pass silently breaks the entire algorithm — the bug won't surface on any test with "lucky" data, only on inputs where values share low-order digits.