Суть: вставка элемента в соответствующее место в уже отсортированной части массива.

1 шаг – первый элемент уже отсортирован;

2 шаг – берём элемент. Сравниваем его с предыдущими: пока не найдём элемент, меньший, чем текущий, идём влево. Далее 2 варианта:

1. Нашли – вставляем на индекс найденного меньшего плюс один;
2. Не нашли – вставляем в начало массива.

3 шаг – повторить шаг 2 до тех пор, пока не дойдём до конца массива.

Сложность по времени:

Лучший случай: $O(n)$ массив уже отсортирован, над каждым элементом, кроме первого будет производиться одна операция, итого: n -1

Средний случай: $O(n^2)$

Худший случай: $O(n^2)$ ***все числа идут не в нужном порядке (например, отсортированы по противоположному критерию), над каждым элементом будет производиться столько операций, сколько элементов перед ним стоит, в итоге: n(n-1)/2 = O(n^2)