Сортировка Шелла (Дональд Шелл, 1959) обобщает сортировку вставками. Вставки двигают элемент всего на одну позицию за раз, поэтому маленькому элементу в конце нужно n шагов. Сортировка Шелла сначала сравнивает элементы на расстоянии gap, потом уменьшает gap, а последний проход с gap = 1 — это обычные вставки по уже почти отсортированному массиву.
Идея
При gap = g элементы a[0], a[g], a[2g], … образуют один подмассив, a[1], a[g + 1], … — другой и так далее. Каждый подмассив сортируется вставками. Массив, в котором отсортированы все подмассивы для шага g, называют g-отсортированным. Он остаётся g-отсортированным и после сортировки с меньшим шагом, поэтому каждый проход только помогает.
a = [23, 12, 1, 8, 34, 54, 2, 3]
n = len(a)
for gap in (4, 2, 1):
for i in range(gap, n):
x = a[i]
j = i
while j >= gap and a[j - gap] > x:
a[j] = a[j - gap]
j -= gap
a[j] = x
print("gap", gap, a)