Быстрая сортировка (merge / quick)

O(n log n)

Сортируем за O(n log n) методом разделяй-и-властвуй: сортировка слиянием делит массив пополам и сливает две отсортированные половины, быстрая сортировка делит вокруг опорного элемента и рекурсивно обрабатывает обе части.

Сигналы

сортировка массива реального размера (тысячи+)нужна гарантированная или ожидаемая O(n log n)сортировка как подготовительный шаг перед другим алгоритмом (два указателя, жадный, сканирующая прямая)нужна стабильность (сортировка слиянием) или сортировка на месте (быстрая сортировка)просто «отсортируй это» без намёка на малое n или особые ключи

Шаблон

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = arr.length >> 1;
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    const out = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        out.push(left[i] <= right[j] ? left[i++] : right[j++]);
    }
    return out.concat(left.slice(i), right.slice(j));
}

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

Элементарные сортировки: Для реального n (тысячи и больше) проход за O(n^2) слишком медленный. Элементарные сортировки имеют смысл только для маленького или почти отсортированного входа; иначе нужна сортировка слиянием или быстрая сортировка.
Сортировка без сравнений (подсчётом/поразрядная): Если ключи - целые числа в небольшом диапазоне, сортировка подсчётом или поразрядная обгоняет O(n log n), вообще не сравнивая элементы. Сортировка сравнениями - выбор по умолчанию только когда диапазон ключей не мал и не известен заранее.

n до ~1e5..1e6, произвольные сравнимые элементы -> O(n log n) время. Большое n без намёка на маленький целочисленный диапазон ключей - сигнал сюда, а не к O(n^2) или сортировке без сравнений.

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