Сортировка вставками: как работает, сложность и код на Python

Коротко

Главное отличие от других квадратичных сортировок: на почти отсортированных данных работает за линейное время. Поэтому её используют внутри промышленных алгоритмов — например, в Timsort, который стоит за sorted() в Python.

Как это работает

Представьте, что вы разбираете карты в руке. Берёте очередную карту и вставляете её на нужное место среди уже разобранных — сдвигая остальные вправо. Ровно это и делает алгоритм.

Массив мысленно делится на две части: слева отсортированная, справа ещё нет. На каждом шаге берём первый элемент правой части и «проваливаем» его влево, пока он не встанет на своё место.

Разберём на массиве [5, 2, 4, 6, 1]:

[5 | 2, 4, 6, 1]   отсортирована только «5»
[2, 5 | 4, 6, 1]   2 меньше 5 → сдвинули 5, вставили 2
[2, 4, 5 | 6, 1]   4 встала между 2 и 5
[2, 4, 5, 6 | 1]   6 больше всех → осталась на месте
[1, 2, 4, 5, 6]    1 меньше всех → уехала в начало

Обратите внимание на предпоследний шаг: элемент 6 уже стоял правильно, и мы не сделали ни одного сдвига. Именно поэтому на отсортированных данных алгоритм такой быстрый.

Код на Python

def insertion_sort(arr: list[int]) -> list[int]:
    # начинаем со второго элемента: первый уже «отсортирован»
    for i in range(1, len(arr)):
        key = arr[i]      # элемент, который вставляем
        j = i - 1

        # сдвигаем вправо всё, что больше key
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key  # нашли место — вставляем

    return arr


print(insertion_sort([5, 2, 4, 6, 1]))  # [1, 2, 4, 5, 6]

Ключевой момент — мы не меняем элементы местами, а именно сдвигаем. Обмен через swap потребовал бы трёх присваиваний вместо одного, а здесь key уже лежит в переменной, и его достаточно записать один раз в конце.

То же на JavaScript

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;
}

insertionSort([5, 2, 4, 6, 1]); // [1, 2, 4, 5, 6]

Почему сложность именно такая

Худший случай. Массив отсортирован по убыванию — каждый новый элемент нужно протащить через всю отсортированную часть. Получается 1 + 2 + 3 + … + (n−1) сдвигов, это n(n−1)/2, то есть O(n²).

Лучший случай. Массив уже отсортирован — условие arr[j] > key ложно сразу, внутренний цикл не выполняется ни разу. Остаётся только внешний проход: O(n). Ни быстрая сортировка, ни сортировка слиянием такого не умеют — они честно отработают свои O(n log n).

В среднем каждый элемент проходит примерно половину отсортированной части, что даёт те же O(n²), только с меньшей константой.

Устойчивость: что это и зачем

Сортировка называется устойчивой, если элементы с одинаковыми ключами сохраняют исходный порядок. Сортировка вставками устойчива — потому что в условии стоит строгое arr[j] > key. Равный элемент не сдвигается, и новый встаёт после него.

Если поменять условие на arr[j] >= key, устойчивость сломается. Это не абстракция: при сортировке списка сотрудников сначала по отделу, потом по зарплате устойчивость — единственное, что сохраняет результат первой сортировки.

Когда её реально применяют

Сама по себе на больших массивах она медленная. Но у неё есть три ниши, где она незаменима.

Маленькие массивы. На 10–50 элементах она обгоняет быструю сортировку, потому что не тратится на рекурсию и выбор опорного элемента. Поэтому промышленные реализации quicksort и mergesort переключаются на вставки, когда подотрезок стал коротким.

Почти отсортированные данные. Если в массиве переставлено несколько элементов, алгоритм отработает почти за O(n).

Потоковые данные. Элементы приходят по одному, и каждый нужно сразу поставить на место в уже отсортированный список. Сортировка вставками работает именно так по своей природе — в отличие от слияния, которому нужен весь массив целиком.

Сравнение с соседями

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

Частые ошибки

Цикл с нуля вместо единицы. Начинать надо с i = 1: первый элемент уже считается отсортированным сам по себе.

Проверка границы после сравнения. В условии while j >= 0 and arr[j] > key порядок важен. Если поменять части местами, при j == -1 произойдёт обращение к arr[-1] — в Python это молча возьмёт последний элемент и даст неверный результат, а не ошибку.

Вставка в arr[j] вместо arr[j + 1]. Цикл заканчивается, когда j уже ушёл на позицию левее нужной, поэтому вставлять надо в следующую ячейку.

Что запомнить

• Алгоритм вставляет каждый элемент на своё место в отсортированной левой части, сдвигая остальные.
• O(n²) в среднем, но O(n) на почти отсортированных данных — её главное преимущество.
• Устойчивая и не требует дополнительной памяти.
• Используется внутри Timsort и других промышленных сортировок для коротких подотрезков.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→