Сортировка Шелла

Сортировка Шелла улучшает сортировку вставками: сначала сравниваются элементы на большом расстоянии (шаге), затем шаг постепенно уменьшается до 1. Это быстро убирает «далёкие» инверсии и снижает число сдвигов.

Сложность: зависит от последовательности шагов — типично около O(n^1.5), в худшем случае хуже. Память: O(1), сортировка на месте, неустойчивая.

def shell_sort(a):
    n = len(a)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            tmp, j = a[i], i
            while j >= gap and a[j - gap] > tmp:
                a[j] = a[j - gap]
                j -= gap
            a[j] = tmp
        gap //= 2
    return a