Insertion sort moves each value one slot at a time, so a small value far to the right takes many steps. Shell sort first runs insertion sort on values 4 apart, then with the gap halved, and finally with gap 1, which is plain insertion sort on a nearly sorted array.
Shell sort on 23, 5, 42, 8, 16, 4, 15, 9 with a first gap of 4.
Gap 4: compare index 0 (23) with index 4 (16), 4 apart. 23 > 16, so swap them and keep stepping back by 4.
Compare 23 and 16, 4 apart: swap.
Gap 4: compare index 1 (5) with index 5 (4), 4 apart. 5 > 4, so swap them and keep stepping back by 4.
Compare 5 and 4, 4 apart: swap.
Gap 4: compare index 2 (42) with index 6 (15), 4 apart. 42 > 15, so swap them and keep stepping back by 4.
Compare 42 and 15, 4 apart: swap.
Gap 4: compare index 3 (8) with index 7 (9), 4 apart. In order, so index 7 is placed for this gap.
Compare 8 and 9, 4 apart: keep.
Gap 2: compare index 0 (16) with index 2 (15), 2 apart. 16 > 15, so swap them and keep stepping back by 2.
Compare 16 and 15, 2 apart: swap.
Gap 2: compare index 1 (4) with index 3 (8), 2 apart. In order, so index 3 is placed for this gap.
Compare 4 and 8, 2 apart: keep.
Gap 2: compare index 2 (16) with index 4 (23), 2 apart. In order, so index 4 is placed for this gap.
Compare 16 and 23, 2 apart: keep.
Gap 2: compare index 3 (8) with index 5 (5), 2 apart. 8 > 5, so swap them and keep stepping back by 2.
Compare 8 and 5, 2 apart: swap.
Gap 2: compare index 1 (4) with index 3 (5), 2 apart. In order, so index 5 is placed for this gap.
Compare 4 and 5, 2 apart: keep.
Gap 2: compare index 4 (23) with index 6 (42), 2 apart. In order, so index 6 is placed for this gap.
Compare 23 and 42, 2 apart: keep.
Gap 2: compare index 5 (8) with index 7 (9), 2 apart. In order, so index 7 is placed for this gap.
Compare 8 and 9, 2 apart: keep.
Gap 1: compare index 0 (15) with index 1 (4), 1 apart. 15 > 4, so swap them and keep stepping back by 1.
Compare 15 and 4, 1 apart: swap.
Gap 1: compare index 1 (15) with index 2 (16), 1 apart. In order, so index 2 is placed for this gap.
Compare 15 and 16, 1 apart: keep.
Gap 1: compare index 2 (16) with index 3 (5), 1 apart. 16 > 5, so swap them and keep stepping back by 1.
Compare 16 and 5, 1 apart: swap.
Gap 1: compare index 1 (15) with index 2 (5), 1 apart. 15 > 5, so swap them and keep stepping back by 1.
Compare 15 and 5, 1 apart: swap.
Gap 1: compare index 0 (4) with index 1 (5), 1 apart. In order, so index 3 is placed for this gap.
Compare 4 and 5, 1 apart: keep.
Gap 1: compare index 3 (16) with index 4 (23), 1 apart. In order, so index 4 is placed for this gap.
Compare 16 and 23, 1 apart: keep.
Gap 1: compare index 4 (23) with index 5 (8), 1 apart. 23 > 8, so swap them and keep stepping back by 1.
Compare 23 and 8, 1 apart: swap.
Gap 1: compare index 3 (16) with index 4 (8), 1 apart. 16 > 8, so swap them and keep stepping back by 1.
Compare 16 and 8, 1 apart: swap.
Gap 1: compare index 2 (15) with index 3 (8), 1 apart. 15 > 8, so swap them and keep stepping back by 1.
Compare 15 and 8, 1 apart: swap.
Gap 1: compare index 1 (5) with index 2 (8), 1 apart. In order, so index 5 is placed for this gap.
Compare 5 and 8, 1 apart: keep.
Gap 1: compare index 5 (23) with index 6 (42), 1 apart. In order, so index 6 is placed for this gap.
Compare 23 and 42, 1 apart: keep.
Gap 1: compare index 6 (42) with index 7 (9), 1 apart. 42 > 9, so swap them and keep stepping back by 1.
Compare 42 and 9, 1 apart: swap.
Gap 1: compare index 5 (23) with index 6 (9), 1 apart. 23 > 9, so swap them and keep stepping back by 1.
Compare 23 and 9, 1 apart: swap.
Gap 1: compare index 4 (16) with index 5 (9), 1 apart. 16 > 9, so swap them and keep stepping back by 1.
Compare 16 and 9, 1 apart: swap.
Gap 1: compare index 3 (15) with index 4 (9), 1 apart. 15 > 9, so swap them and keep stepping back by 1.
Compare 15 and 9, 1 apart: swap.
Gap 1: compare index 2 (8) with index 3 (9), 1 apart. In order, so index 7 is placed for this gap.
Compare 8 and 9, 1 apart: keep.
Sorted with 27 comparisons and 15 swaps. The big gaps did the long-distance moves cheaply, so the final gap-1 pass found almost everything in place. With these halving gaps shell sort is O(n^2) in the worst case but far faster than insertion sort in practice. Better gap sequences reach O(n^1.3).
Sorted after 27 comparisons and 15 swaps.