Вот алгоритм метода из Википедии:
Код:
Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n]
for i = 2, 3, ..., n:
key := A[i]
j := i - 1
while j > 0 and A[j] > key:
A[j + 1] := A[j]
j := j - 1
A[j + 1] := key
Идея такая. Берётся первый элемент (А1). Затем находится место для элемента А2 (перед А1 или после), затем - для А3 (в начале, в середине или в конце) и так далее. Как находится место для нового элемента, если К элементов уже находятся по порядку (возрастания)? Начиная с последнего (К-го) элементы сдвигаются вперёд (их индекс увеличивается), пока не выполнится условие, что в образовавшуюся дыру можно вставить (К+1)-й элемент (он обозначен
key), так чтобы он был
на месте, т.е. он был больше соседей с меньшими индексами, но меньше соседей с большими индексами.
Хотя не знаю, для чего вам дают этот метод, ведь он не самый быстрый. Наверное, для вас других заданий не могут придумать.