Сортировка вставками
Берём элемент и вставляем на место в отсортированной части — как карты в руке.
1function insertionSort(a: number[]): number[] {2 for (let i = 1; i < a.length; i++) {3 let j = i4 while (j > 0 && a[j - 1] > a[j]) {5 const t = a[j]6 a[j] = a[j - 1]7 a[j - 1] = t8 j--9 }10 }11 return a12}Проблема
Поддерживать отсортированный префикс массива: каждый новый элемент «взять и довставить» в уже упорядоченную часть, сдвигая больших соседей вправо.
Что вы видите
Массив с растущей лаймовой рамкой «отсортировано». Взятый элемент подсвечен; пока слева от него кто-то больше — они меняются местами, и элемент сползает на своё место.
Как это работает
Как игрок собирает карты: каждый новый элемент вставляется в уже сложенную часть. На почти отсортированных данных — почти без сдвигов, O(n). В худшем случае (обратный порядок) — O(n²). На малых и почти упорядоченных массивах insertion sort быстрее «квадратичных» коллег, поэтому его прячут внутри гибридов вроде Timsort.
Пошаговый разбор
- 01
Префикс
Первый элемент сам по себе отсортирован.
- 02
Взять элемент
a[i] — кандидат на вставку.
- 03
Сдвиги
Пока сосед слева больше — обмен, элемент идёт влево.
- 04
Место найдено
Слева не больше — префикс вырос до i+1.
Complexity и ограничения
Стабильная сортировка. Почти отсортированный массив — O(n); обратный порядок — O(n²).
Edge cases
- Отсортирован
Одно сравнение на элемент, ноль сдвигов — O(n).
- Обратный порядок
Максимум сдвигов, i сдвигов на i-й элемент.
- Малые массивы
До ~10-20 элементов часто быстрее Quick/Merge — поэтому живёт внутри Timsort.
Где встречается в реальности
Timsort
Гибрид слияний и вставок — стандарт сортировки в Python и Java.
Живые данные
Поток, где новые значения почти на месте: логи, тики, инкрементальные обновления.
Карты в руке
Буквально так человек сортирует карты.
Связанные алгоритмы
«Как игрок собирает карты — и почему это в Python»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.