Алгоритм вставок (InsertionSort)

Идея заключается в следующем. Пусть к некоторому моменту работы алгоритма первые k элементов массива уже отсортированы, т.е. расположены по возрастанию. На очередном проходе постараемся добиться, чтобы стали отсортированными k+1 элементов. Для этого запомним значение элемента a_k+1 в рабочей переменной r и будем сравнивать r со значениями элементов a_k, a_k–1, a_k–2 и т.д. Если значение сравниваемого элемента больше r, то этот элемент перемещается на одну позицию правее. Сравнения продолжаются, пока не будет найдено место, куда должен быть помещен элемент r (это случится либо когда очередной сравниваемый элемент меньше или равен r, либо когда мы дойдем до начала массива).

Таким образом, на очередном проходе отсортированная часть массива удлиняется на 1 элемент. Начав со значения k = 1, можно за n–1 проход отсортировать весь массив.

Алгоритм вставок можно немного улучшить, если выбирать место для вставки k+1-го элемента не последовательным просмотром элементов от k до 1, а бинарным поиском по уже отсортированной части масива (т.е. сравнить r с элементом j = (k+1) div 2, затем продолжить поиск на одном из интервалов [1.. j–1] или [j+1.. k] и т.д.). Этот подход, называемый алгоритмом бинарных вставок, позволяет существенно сократить число сравнений, но, к сожалению, не влияет на число перестановок.