Вопрос №155

Сортировка. Вставка.

Делим массив на две части (левую и правую). Левую часть считаем отсортированной. Изначально первый элемент массива оставляем в левой части, все остальное относим к правой (не отсортированной). Начинаем перемещаться по не отсортированной части. Берем первый элемент, и попарно сравнивая с соседними, ищем ему место в отсортированной части. Например, имеем массив [ 4 6 2 1 ]. Выполняем сортировку:

1. Делим на 2 части: [ 4 | 6 2 1 ].
2. Берем элемент 6 и ставим его на подходящее место в отсортированной части: [ 4 6 | 2 1 ].
3. Ставим на свое место элемент 2: [ 2 4 6 | 1 ].
4. Ставим на свое место элемент 1: [ 1 2 4 6 ].