Сортування методом вставки
Один елемент завжди можна вважати відсортованим масивом довжини 1.
Розглядаючи послідовно решту елементів масиву будемо включати їх у відсортовану частину масиву, ставлячи на потрібне місце, тобто не порушуючи відсортованості цієї частини. Повторивши операцію включення n-1 раз, одержимо відсортований масив.
На i-му кроці відсортованим вважається масив a[1] .. a[i], а вставляємо елемент a[i+1]. Вставляти можна, послідовно порівнюючи a[i+1] з a[1], a[2],..., поки не знайдеться "дірка" j
a[j] Ј a[i+1] Ј a[j+1].
Тоді слід зсунути елементи a[j+1] .. a[i] вправо на один елемент, а a[i+1] записати на місце a[j+1].
Може статися, що a[i+1] більше за будь-який з членів відсортованої частини. Тоді дірку не буде знайдено. Тому слід контролювати номер j, щоб не вийти за межи відсортованої частини.