Сортировка вставками работает следующим образом: 2

1. Массив делят на две части — отсортированную и неотсортированную. 2
2. Из неотсортированной части извлекают любой элемент. 2
3. Поскольку другая часть массива отсортирована, то в ней достаточно быстро можно найти своё место для этого извлечённого элемента. 2
4. Элемент вставляют куда нужно, в результате чего отсортированная часть массива увеличивается, а неотсортированная уменьшается. 2

Обобщённый алгоритм: 4

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

Этот процесс повторяют до тех пор, пока набор входных данных не будет исчерпан. 1