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

---

Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов^[1]. Вычислительная сложность — ${\displaystyle O(n^{2})}$.

На вход алгоритма подаётся последовательность ${\displaystyle n}$ чисел: ${\displaystyle a_{1},a_{2},...,a_{n}}$. Сортируемые числа также называют ключами. Входная последовательность на практике представляется в виде массива с ${\displaystyle n}$ элементами. На выходе алгоритм должен вернуть перестановку исходной последовательности ${\displaystyle a_{1}^{'},a_{2}^{'},...,a_{n}^{'}}$, чтобы выполнялось следующее соотношение ${\displaystyle a_{1}^{'}\leqslant a_{2}^{'}\leqslant ...\leqslant a_{n}^{'}}$^[2].

В начальный момент отсортированная последовательность пуста. На каждом шаге алгоритма выбирается один из элементов входных данных и помещается на нужную позицию в уже отсортированной последовательности до тех пор, пока набор входных данных не будет исчерпан. В любой момент времени в отсортированной последовательности элементы удовлетворяют требованиям к выходным данным алгоритма^[3].

Данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей^[4].

---