Shell sort (Donald Shell, 1959) generalises insertion sort. Insertion sort moves an element only one position at a time, so a small element at the end needs n steps. Shell sort first compares elements at a distance gap, then shrinks the gap, and the last pass with gap = 1 is plain insertion sort over an already nearly sorted array.

Shell sort on 23 12 1 8 34 54 2 3
Shell sort on 23 12 1 8 34 54 2 3

The idea

With gap = g the elements a[0], a[g], a[2g], … form one subarray, a[1], a[g + 1], … another, and so on. Each subarray is sorted by insertion. An array in which every subarray for gap g is sorted is called g-sorted. A g-sorted array stays g-sorted after sorting with a smaller gap, so every pass only helps.

python
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)