Элементарные сортировки (выбором, пузырьком, вставками)

O(n^2)

Сортируем простыми проходами с вложенными циклами: раз за разом выбираем следующий наименьший элемент, меняем местами соседние элементы не по порядку или вставляем каждый элемент на его место среди уже отсортированных.

Сигналы

n маленькое (десятки или пара сотен)массив уже почти отсортировансортировка на месте с O(1) дополнительной памятиучебный/собеседовательный вопрос о механике сортировкиважна стабильность, а простота приемлема

Шаблон

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        const key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

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

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

n маленькое (примерно до пары сотен) или почти отсортировано -> O(n^2) время приемлемо, O(1) память. Как только в условии n указано в тысячах и больше, это перестаёт быть ответом.

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