Сортировка вставкой очень похожа на сортировку пузырьком, но при этом она значительно лучше последней и имеет скорость выполнения выше -линейно логарифмическую. В чем смысл сортировки вставкой как он происходит. 

  • В худшем и среднем случае: O(n**2) квадратичная сложность  нужен обход двух циклов 

  • В лучшем случае O(n) -  если список уже отсортирован

 

Как работает сортировка вставками?

  1. Список делится на две части:

    • Отсортированная (изначально это первый элемент).

    • Неотсортированная (все остальные элементы).

  2. Последовательно берём элементы из неотсортированной части и вставляем их в правильное место в отсортированной части.

  3. Процесс повторяется, пока весь список не будет отсортирован

def insert_sorting(list_):
    for i in range(1, len(list_)):  # Начинаем со второго элемента
        value = list_[i]  # Текущий элемент для вставки
        while i > 0 and list_[i-1] > value:  # Пока предыдущий элемент больше
            list_[i] = list_[i-1]  # Сдвигаем элемент вправо
            i -= 1  # Двигаемся влево по отсортированной части
        list_[i] = value  # Вставляем `value` на найденное место
    return list_

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

  1. Берём элемент list_[i] (начиная с i = 1).

  2. Сравниваем его с предыдущими элементами (уже отсортированными).

  3. Если предыдущий элемент больше, сдвигаем его вправо.

  4. Когда находим правильное место, вставляем value.

Когда использовать сортировку вставками?

✔ Маленькие массивы (до 100 элементов).
✔ Частично упорядоченные данные (например, добавление новых элементов в почти отсортированный список).
✔ Когда важна стабильность (сохранение порядка равных элементов).