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

Алгоритм

Префиксом длины $i$ будем называть первые $i$ элементов массива.

Тогда пусть на $i$-ом шаге у нас уже будет отсортирован префикс до $i$-го элемента. Чтобы этот префикс увеличить, нужно взять элемент, идущий после него, и менять с левым соседом, пока этот элемент наконец не окажется больше своего левого соседа. Если в конце он больше левого соседа, но меньше правого - это значит, что мы правильно вставили этот элемент в отсортированную часть массива.

Yet another красивая визуализация (вкладка INS)

Оценка времени работы

Так как каждое число перемещается влево не более $N$ раз, то время работы составляет $O(N^2)$.

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko