Сортировка вставками (объяснение алгоритма)
Как и сортировка выборкой, этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Алгоритм перебирает второй сегмент и вставляет текущий элемент в правильную позицию первого сегмента.
Предполагается, что первый элемент списка отсортирован. На каждом шаге переходим к следующему элементу, обозначим его х. Если х больше прошлого элемента, оставляем x на своём месте. Если x меньше прошлого элемента, копируем прошлый элемент на вторую позицию, а х устанавливаем на его место.
Переходя к другим элементам несортированного сегмента, перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше x или не дойдём до конца списка. В первом случае x помещается на правильную позицию.
Время сортировки вставками в среднем равно O(n²), где n — количество элементов списка.
