Сортировка вставками работает как раскладывание игральных карт в руке: левая часть уже отсортирована, а каждый новый элемент вставляется на своё место в ней. Алгоритм простой, устойчивый, работает на месте и очень быстр на почти отсортированных данных. Термины (устойчивость, адаптивность) см. в уроке свойства сортировок.
Алгоритм и инвариант
Берём x = a[i] и сдвигаем каждый элемент отсортированной части a[:i], который больше x, на одну позицию вправо. Затем ставим x в освободившееся место. Инвариант: перед шагом i часть a[:i] состоит из исходных первых i элементов и отсортирована.
a = [5, 2, 4, 6, 1, 3]
for i in range(1, len(a)):
x = a[i]
j = i - 1
while j >= 0 and a[j] > x:
a[j + 1] = a[j]
j -= 1
a[j + 1] = x
print("insert", x, "->", a)insert 2 -> [2, 5, 4, 6, 1, 3]
insert 4 -> [2, 4, 5, 6, 1, 3]
insert 6 -> [2, 4, 5, 6, 1, 3]
insert 1 -> [1, 2, 4, 5, 6, 3]
insert 3 -> [1, 2, 3, 4, 5, 6]Реализация
Условие j >= 0 and a[j] > x сначала проверяет границу, а потом сравнивает. Строгое > не двигает равные элементы, поэтому сортировка устойчива.
