2.2.2 — как обойти границу Ω(n log n), не нарушая доказанную теорему2.2.2 — beating the Ω(n log n) bound without breaking the proven theorem
Теорема из 2.2.1 доказывает, что сортировка сравнением не может быть быстрее Ω(n log n) — но это утверждение только про алгоритмы, которые сравнивают элементы попарно. Если про значения известно что-то ещё (например, что это целые числа в диапазоне [0, k)), можно вообще не сравнивать — и получить линейное время. Здесь: counting sort, radix sort, bucket sort с нуля.The theorem from 2.2.1 proves that comparison sorting can't beat Ω(n log n) — but that claim only applies to algorithms that compare elements pairwise. If something more is known about the values (e.g. that they're integers in a range [0, k)), comparisons can be skipped entirely — yielding linear time. Here: counting sort, radix sort, and bucket sort from scratch.
Нижняя граница из 2.2.1 доказана строго для модели дерева решений, где единственная разрешённая операция — сравнение двух элементов. Counting sort, radix sort и bucket sort нарушают саму предпосылку доказательства: они ни разу не спрашивают "a < b?" — вместо этого они используют значение элемента напрямую как индекс (счётчик, номер корзины, разряд числа). Раз модель другая, теорема о ней ничего не говорит — это не парадокс и не "более умный" алгоритм для той же задачи, а решение немного другой задачи: сортировки не произвольно сравнимых объектов, а объектов с известной числовой структурой.The lower bound from 2.2.1 is proven strictly for the decision-tree model, where the only allowed operation is comparing two elements. Counting sort, radix sort, and bucket sort break the proof's very premise: they never ask "a < b?" — instead they use an element's value directly as an index (a counter, a bucket number, a digit of the number). Since the model is different, the theorem says nothing about it — this isn't a paradox or a "smarter" algorithm for the same problem, but a solution to a slightly different problem: sorting not arbitrary comparable objects, but objects with known numeric structure.
теорема о нижней границе привязана к модели вычисления, а не к задаче сортировки как таковойthe lower-bound theorem is tied to the computational model, not to the sorting task itself
Все три эксплуатируют структуру значений напрямую, вместо сравнения; полный разбор с диаграммами, кодом и примерами — на отдельной странице по ссылке в названии.All three exploit the values' structure directly instead of comparing them; the full writeup with diagrams, code, and examples is on its own page via the name link.
Порядок в таблице — это и порядок усложнения требований к входу: counting sort нужен только маленький диапазон значений, radix sort снимает это ограничение ценой разбиения на разряды, bucket sort идёт дальше и работает с вещественными числами, но полагается на равномерность распределения, а не гарантирует линейное время безусловно. Четвёртая карточка (пока без ссылки) — pigeonhole sort, вырожденный случай counting sort, который стоит увидеть отдельно именно чтобы не спутать его с общим случаем.The table's order also tracks increasing demands on the input: counting sort only needs a small value range, radix sort removes that constraint at the cost of splitting into digits, bucket sort goes further and works with real numbers, but relies on a uniform distribution rather than guaranteeing linear time unconditionally. The fourth card (not yet linked) is pigeonhole sort, a degenerate case of counting sort worth seeing separately precisely so it isn't confused with the general case.
Возраст сотрудников (0-120) или оценки студентов (0-100) — классический случай маленького k: counting sort здесь строго быстрее любой сортировки сравнением, и это не гипотетический пример, а стандартная оптимизация в аналитических пайплайнах, работающих с ограниченными категориальными шкалами.Employee ages (0-120) or student grades (0-100) are a textbook small-k case: counting sort here is strictly faster than any comparison sort, and this isn't a hypothetical example but a standard optimization in analytics pipelines working with bounded categorical scales.
Сортировка ДНК-последовательностей фиксированной длины (алфавит из 4 символов: A, C, G, T) естественно ложится на radix sort по позициям — каждый символ трактуется как "разряд", и вся строка сортируется за линейное от суммарной длины входа время, без единого сравнения строк целиком.Sorting fixed-length DNA sequences (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 string set is sorted in time linear in the total input length, without a single whole-string comparison.
IPv4-адреса — это 32-битные числа фиксированной длины, что делает их идеальным кандидатом для radix sort по байтам (4 прохода по 8 бит); сетевое оборудование, сортирующее или группирующее пакеты по адресу, использует именно эту фиксированную структуру, а не сравнение адресов как произвольных чисел.IPv4 addresses are fixed-length 32-bit numbers, making them an ideal candidate for byte-wise radix sort (4 passes of 8 bits each); network hardware that sorts or groups packets by address exploits exactly this fixed structure rather than comparing addresses as arbitrary numbers.
Значения яркости пикселей (обычно 0-255, равномерно или почти равномерно распределённые в естественных изображениях) — хороший кандидат для bucket sort при построении гистограмм или медианных фильтров, где известный ограниченный диапазон значений заменяет необходимость в сравнении.Pixel brightness values (typically 0-255, roughly uniformly distributed in natural images) are a good bucket-sort candidate when building histograms or median filters, where a known bounded value range replaces the need for comparison.
Прозрачные объекты в рендеринге сортируются по глубине (z-координате, часто квантованной до фиксированной битовой ширины) перед отрисовкой; GPU-реализации radix sort хорошо параллелизуются именно потому, что каждый проход по разряду — это независимый подсчёт по корзинам, без последовательной зависимости, характерной для сравнения элементов попарно.Transparent objects in rendering are sorted by depth (z-coordinate, often quantized to a fixed bit width) before drawing; GPU radix-sort implementations parallelize well precisely because each digit pass is an independent bucket count, without the sequential dependency characteristic of pairwise comparison.
Использование нестабильной сортировки (например, quicksort) внутри одного прохода radix sort молча ломает весь алгоритм — итоговый результат может оказаться неотсортированным, при этом ошибка не проявится ни на каком unit-тесте с достаточно "удачными" данными, только на входах, где значения совпадают в младших разрядах.Using an unstable sort (e.g. quicksort) within a single radix-sort pass silently breaks the entire algorithm — the final result can end up unsorted, and the bug won't surface in any unit test with sufficiently "lucky" data, only on inputs where values share low-order digits.
O(n + k) выглядит линейным, но при k ≫ n (например, сортировка 100 чисел из диапазона [0, 10¹²)) память и время фактически определяются k, а не n — здесь radix sort или обычная сортировка сравнением будут быстрее, несмотря на "линейную" асимптотику counting sort.O(n + k) looks linear, but when k ≫ n (e.g. sorting 100 numbers from the range [0, 10¹²)) memory and time are effectively dominated by k, not n — here radix sort or an ordinary comparison sort will be faster despite counting sort's "linear" asymptotics.
Гарантия O(n) для bucket sort — это ожидаемое время при условии равномерного распределения входа; на данных с сильным перекосом (степенное распределение, много повторов) почти все элементы попадают в одну корзину, и сортировка внутри неё деградирует до сложности используемого там алгоритма — важно проверять это предположение перед выбором bucket sort, а не считать его само собой разумеющимся.The O(n) guarantee for bucket sort is expected time conditional on a uniform input distribution; on heavily skewed data (a power-law distribution, many duplicates) nearly all elements land in one bucket, and sorting within it degrades to the complexity of whatever algorithm runs there — this assumption needs checking before picking bucket sort, not taking for granted.