Можно ли быстрее O(n log n)

В предыдущих уроках мы сортировали через сравнения (if a < b). Доказана нижняя граница: любая comparison-based sort требует минимум O(n log n) сравнений в worst case. Доказательство — через decision tree: чтобы различить n! перестановок, нужно дерево высотой log_2(n!) = O(n log n).

Но это нижняя граница только для comparison-based. Если использовать другую модель — извлечение свойств элементов напрямую — можно работать за O(n). Два таких алгоритма: counting sort и radix sort.

Counting sort: подсчёт вхождений

Идея: если все элементы — целые числа в небольшом диапазоне [0, k], можно:

1. Создать массив счётчиков длины k.
2. Пройти по входному массиву, увеличивая счётчик для каждого значения.
3. Восстановить отсортированный массив, проходя по счётчикам.

def counting_sort(arr: list[int], k: int) -> list[int]:
    """Сортирует массив целых в диапазоне [0, k]. O(n + k)."""
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1

    result = []
    for value in range(k + 1):
        result.extend([value] * count[value])
    return result

print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=8))
# [1, 2, 2, 3, 3, 4, 8]

Сложность: O(n + k). Никаких сравнений вообще.

Когда это быстрее O(n log n)? Когда k = O(n) или меньше. Если k растёт намного быстрее n (например, диапазон 10^18 на массиве 1000 элементов), counting sort деградирует — почти все ячейки счётчика пустые.

Стабильный counting sort

Версия выше дедуплицирует исходные элементы (восстанавливает по значениям). Если элементы — не просто int, а сложные структуры с ключом-int, нужна стабильная версия:

def counting_sort_stable(arr: list, key_fn, k: int) -> list:
    n = len(arr)
    count = [0] * (k + 1)
    for x in arr:
        count[key_fn(x)] += 1

    # cumulative count: count[i] = число элементов с key <= i
    for i in range(1, k + 1):
        count[i] += count[i - 1]

    # обходим arr с конца, чтобы сохранить стабильность
    result = [None] * n
    for x in reversed(arr):
        key = key_fn(x)
        count[key] -= 1
        result[count[key]] = x
    return result

Проход с конца гарантирует, что для двух элементов с одинаковым ключом первый по исходному порядку окажется первым по выходу. Это и есть стабильность.

Применение counting sort

Сценарий 1: возраст пользователей. Возраст — int от 0 до 120. На массиве 10М пользователей counting sort:

• k = 121, n = 10^7,
• время O(n + k) = O(10^7) — десятки миллисекунд,
• comparison-based: O(n log n) = ~2.5 * 10^8 — секунды.

Сценарий 2: количество звёзд в обзоре. Звёзды 1-5. Counting sort за O(n) — лучшее, что можно сделать.

Сценарий 3: status enum. 5-10 возможных значений. Counting идеален.

Сценарий 4: hash в bucket’ы. Если ключи — int, попадающие в ограниченный диапазон, counting sort — это и есть hash без коллизий.

Counting sort недостатки

Не работает на больших диапазонах. Сортировка 1000 int в диапазоне [0, 10^9] через counting — массив счётчиков 10^9 ячеек, 4 ГБ. Невозможно. Нужен radix sort или comparison-based.

Не работает на floats. Counting требует дискретных значений с известным диапазоном.

Не работает на complex objects без явного key. Сравнение «строка vs строка» в comparison sort работает; counting нужен int-ключ.

Radix sort: цифра за цифрой

Идея LSD radix sort:

1. Отсортировать массив по последней цифре через stable counting sort.
2. Отсортировать тот же массив по предпоследней цифре.
3. Продолжать до самой старшей цифры.

Stability counting sort гарантирует, что предыдущие сортировки не нарушаются.

def radix_sort(arr: list[int]) -> list[int]:
    """LSD radix sort для неотрицательных int."""
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    count = [0] * 10
    output = [0] * n
    for x in arr:
        digit = (x // exp) % 10
        count[digit] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for x in reversed(arr):
        digit = (x // exp) % 10
        count[digit] -= 1
        output[count[digit]] = x
    return output

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

Сложность: O(d * (n + b)), где d — число цифр, b — основание (10 для десятичной). Если b = O(n), а d = const, получаем O(n).

В реальности radix sort часто использует основание 256 (один байт) или 65536 (два байта). Для 64-битного int — 8 байтовых проходов.

Применение radix sort

1. Сортировка целочисленных ключей в БД. Postgres использует radix sort для int-ключей в некоторых случаях, когда выгоднее, чем quicksort.

2. Suffix arrays. Сортировка суффиксов строки — основа алгоритмов поиска подстроки.

3. Сортировка float’ов. Float’ы можно сортировать radix-ом, если правильно обрабатывать знак и порядок битов. Используется в high-performance numeric libraries.

4. Spark/Hadoop sort. На больших данных radix sort экономит I/O — данные читаются партиями по «корзинам».

Counting vs radix vs quicksort: сравнение

DE-кейс: сортировка timestamps по дате

Сценарий: 1 миллиард timestamp-ов (микросекунды Unix epoch). Нужно отсортировать перед записью в Parquet.

Если использовать sorted() — O(n log n) ≈ 30 * 10^9 ≈ 30 секунд + большая память.

С radix sort на 64-битных int с основанием 65536 — 4 прохода, O(4 * n) ≈ 4 * 10^9 операций. В теории в ~7-8 раз быстрее.

Но в Python radix sort написать быстро трудно — каждая операция много байт-кода. Поэтому на практике быстрее использовать numpy:

import numpy as np
ts = np.random.randint(0, 10**15, size=10**9, dtype=np.int64)
ts.sort()   # numpy.sort использует introsort или radix внутри

Numpy на больших целочисленных массивах в специальных случаях переключается на radix sort (kind='radix' или автоматически для int).

DE-кейс: сортировка по hash

Сценарий: distribute events по 256 партициям через hash(key) % 256. Это эквивалент counting sort с k=256.

from collections import defaultdict

def partition_events(events, n_partitions=256):
    bins = defaultdict(list)
    for e in events:
        h = hash(e["key"]) % n_partitions
        bins[h].append(e)
    return bins

Это O(n), без сравнений вообще. Стандартная техника shuffle в Spark/Hadoop.

Stability radix sort

LSD radix sort стабилен только если на каждом шаге используется stable counting sort. Это важно: иначе ранние сортировки разрушаются поздними.

Проверка: в нашем коде проход for x in reversed(arr): count[digit] -= 1; output[count[digit]] = x — обратный проход обеспечивает стабильность. Это типичный приём для stable counting sort.

Попробуй сам

import random
import time

def counting_sort(arr, k):
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1
    result = []
    for value in range(k + 1):
        result.extend([value] * count[value])
    return result

# 10М int в диапазоне [0, 100]
N = 10**7
arr = [random.randint(0, 100) for _ in range(N)]

t = time.perf_counter(); counting_sort(arr, 100); print("counting:", time.perf_counter() - t)
t = time.perf_counter(); sorted(arr); print("Timsort:", time.perf_counter() - t)

Ожидаемое:

• counting: 1-2 секунды (Python overhead),
• Timsort: 3-5 секунд (он log n = ~23 сравнения per element).

В numpy:

import numpy as np
arr = np.random.randint(0, 100, size=10**7)
t = time.perf_counter(); np.sort(arr); print(time.perf_counter() - t)
# ~100 мс — numpy на C, причём небольшой диапазон оптимизируется

Counting sort в Python проигрывает Timsort из-за overhead интерпретатора. В numpy/C преимущество counting на узком диапазоне видно.

В следующем модуле — Timsort подробно. Это финальный синтез: insertion + merge + adaptive = главная sorted() в Python.