Сортировка без сравнений (подсчётом / поразрядная)

O(n)

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

Сигналы

ключи - целые числа в небольшом известном диапазонесортировка возрастов, оценок или ограниченных счётчиковнужна O(n), а сравнения - узкое местосортировка по разрядам или ключу фиксированной шириныn большое, но диапазон значений намного меньше n

Шаблон

function countingSort(arr, maxVal) {
    const counts = new Array(maxVal + 1).fill(0);
    for (const x of arr) counts[x]++;
    const out = [];
    for (let v = 0; v <= maxVal; v++) {
        while (counts[v]-- > 0) out.push(v);
    }
    return out;
}

Похоже, но не то

Быстрая сортировка (merge/quick): Сортировки сравнениями в худшем случае никогда не обгонят O(n log n), это доказанная нижняя граница. Подсчёт/поразрядная обгоняют её только за счёт использования небольшого целочисленного диапазона ключей; без этой структуры остаётся merge/quick.

ключи - целые числа, ограниченные k, и k порядка O(n) или меньше -> O(n + k) время, O(n + k) память. Явно указанный малый/известный диапазон ключей (а не просто «n большое») - сигнал сюда, а не к обычной сортировке сравнениями.

Изучить этот паттерн