Можно ли отсортировать быстрее, чем за O(n log n)?

Почему n log n — предел для сравнений. Алгоритм сортировки сравнением можно представить как дерево решений: в каждом узле — сравнение двух элементов, в каждом листе — конкретная перестановка, которая сортирует вход. Различных входов-перестановок n!, и каждая должна вести в свой лист. Двоичное дерево с n! листьями имеет высоту не меньше log₂(n!), а это порядка n log n (по формуле Стирлинга). Высота — число сравнений в худшем случае. Значит, слияние и пирамидальная сортировка асимптотически оптимальны.

Как обойти ограничение — не сравнивать, а использовать структуру ключей:

• сортировка подсчётом — для целых чисел в диапазоне 0..k: считаем, сколько раз встречается каждое значение, затем выписываем по порядку. O(n + k) времени и O(k) памяти. Выгодна, когда k не больше порядка n (оценки, возраст, байты);
• поразрядная (radix) — сортируем устойчиво по каждой цифре, от младшей к старшей, сортировкой подсчётом. O(d·(n + k)), где d — число разрядов. Подходит для целых, строк фиксированной длины, IP-адресов;
• блочная (bucket) — раскладываем по корзинам по значению и сортируем корзины; линейная в среднем для равномерно распределённых чисел.

Ограничения: нужна информация о ключах (целые, диапазон, длина), много памяти при большом k; для произвольных объектов с компаратором остаётся O(n log n).

def counting_sort(a, max_value):
    counts = [0] * (max_value + 1)
    for x in a:
        counts[x] += 1
    return [v for v, c in enumerate(counts) for _ in range(c)]

counting_sort([3, 1, 4, 1, 5, 2], 5)   # [1, 1, 2, 3, 4, 5]