Простая вставка

В этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.

Пусть отсортировано начало массива A [1], A [2],..., A [ i -1], а остаток массива A [ i ],..., A [ n ] содержит неотсортированную часть. На очередном шаге будем включать элемент A [ i ] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A [ i ], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A [ i ]. Но при сдвиге будет потеряно само значение A [ i ], поскольку в эту позицию запишется первый (самый правый – с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A [ i ] в промежуточной переменной. Так как массив из одного элемента можно считать отсортированным, начнем с i =2.

Этот алгоритм также имеет максимальную и среднюю временную сложности, пропорциональные O (n ²), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет временную сложность T_min (n), пропорциональную O (n). Алгоритм сохраняет порядок элементов с одинаковыми значениями.