Сортировка вставками

Сортировка вставками (Insertion Sort): идея «карточной игры», пошаговый разбор, код на Python, сложность O(n²) и O(n) на почти отсортированных данных.

Сортировка вставками строит отсортированный массив по одному элементу: берёт очередной элемент и «вставляет» его на правильное место среди уже упорядоченных. Так раскладывают карты в руке.

Сложность: O(n²) в среднем и худшем случае; O(n) в лучшем (уже отсортированный массив).

Идея алгоритма

Слева растёт отсортированная часть. Для каждого нового элемента мы «сдвигаем» уже стоящие элементы вправо до тех пор, пока не найдём правильное место для вставки. Метафора: как вставить новую карту в уже упорядоченный веер в руке.

Пошаговый разбор

Массив [7, 2, 4, 1, 5]:

Вставляем	Ключ	Массив после вставки
i=1	2	[2, 7, 4, 1, 5]
i=2	4	[2, 4, 7, 1, 5]
i=3	1	[1, 2, 4, 7, 5]
i=4	5	[1, 2, 4, 5, 7]

Код

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]          # элемент для вставки
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]   # сдвигаем вправо
            j -= 1
        arr[j + 1] = key          # вставляем на нужное место
    return arr

data = [7, 2, 4, 1, 5]
print(insertion_sort(data))

Вывод:

[1, 2, 4, 5, 7]

Сложность и свойства

Случай	Сравнений	Присвоений
Лучший (отсортирован)	O(n)	O(1)
Средний	O(n²)	O(n²)
Худший (обратный порядок)	O(n²)	O(n²)

Память: O(1) — in-place. Алгоритм устойчивый: равные элементы не меняют взаимного порядка.

На почти отсортированных данных (например, лог-файлах, куда новые записи добавляются в конец) insertion sort работает практически за O(n) и обгоняет «умные» алгоритмы за счёт крайне низких констант.

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

Insertion sort — отличный выбор для:

маленьких массивов (до ~30 элементов);
почти отсортированных данных;
онлайн-сортировки, когда элементы поступают по одному.

Именно поэтому гибридные алгоритмы (Timsort в Python, Introsort в C++) переключаются на insertion sort для маленьких подмассивов.

Коротко

Insertion sort берёт очередной элемент и вставляет его в правильное место в уже отсортированной части.
O(n²) в среднем и худшем, O(n) в лучшем случае.
In-place, устойчивый.
Эффективен на маленьких и почти отсортированных массивах; используется как финальный шаг в Timsort.