Сортировка вставками

Дан произвольный массив из n элементов. Нужно упорядочить массив по неубыванию элементов.

Идея алгоритма: элементы последовательно просматриваются и каждый элемент встает на место, среду уже отсортированных.

Псевдокод

for i = 1 to n - 1:
    j = i
    while j > 0 and a[j-1] > a[j]:
        swap(a[j-1], a[j])
        j -= 1

Визуализация