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

Сортировка вставками элементов относится к наиболее очевидным методам (алгоритм 5.1). Для компактности алгоритма вводится фиктивный элемент значение которого устанавливается равным Сортировка проходит цикл для для каждого элемент вставляется в свое правильное место среди При вставке элемент временно размещается в и просматриваются имена они сравниваются с и сдвигаются вправо, если обнаруживается, что они больше Имеется фиктивный элемент значение которого служит для остановки просмотра слева.

Алгоритм 5.1. Сортировка вставками

(см. скан)

Сложность алгоритма определяется числом проверок условия в цикле. Сравнение для конкретного выполняется раз, где число элементов, больших и стоящих слева от него, это число инверсий, у которых второй элемент Числа составляют таблицу инверсий а так как то в худшем случае сортировка элементов потребует) сравнений. Сложность сортировки вставками является квадратичной.