Пояснение алгоритма

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

1.) Мы считаем, что первый элемент в списке уже отсортирован.
2.) Берём следующий элемент из неотсортированной части и сравниваем его с предыдущим(т.е с элементом из отсортированной части).
3.) Если условие сортировки выполняется, то мы меняем их местами, в обратном случае считаем элемент отсортированным.
4.) Шагами 2 и 3 проходим весь список.

Реализация алгоритма на примере с массивом чисел

for (i = 1; i < n; i++) {               
    j = i;                              //тут мы ставим ограничение, чтобы при сравнении элементов не уйти за границу массива
    while ((j > 0) && (s[j] < s[j-1])) {
        swap(&s[j], &s[j-1]);
        j = j - 1;
    }
}

Сложность алгоритма

Сложность этого алгоритма O(n^2), ведь в наихудшем случае при сортировке количество операций будет равно сумме чисел от 0 до n-1.(т.е n*(n-1)/2).

Дополнительно хочется сказать, что на скорость алгоритма сильно влияет эффективность самих структур данных. Например в случаи с сбалансированным двоичным деревом время поиска 1 элемента будет равно O(log(n)), значит n элементов - O(n*log(n)). Если дополнительно пользоваться симметричным обходом то время будет линейно - O(n).

Ссылки на литературу

[ 03.04.108 Двоичные деревья поиска ]
[ Скиена 2022 с. 108 - 114]