Shell sort generalizes insertion sort by sorting elements that are gap positions apart, then shrinking the gap until it reaches 1. By the time gap = 1, the array is nearly sorted and the final insertion-sort pass is fast. The exact complexity depends on the gap sequence chosen.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n log n) |
Θ(n(log n)²) |
O(n(log n)²) |
O(1) |
Pick a decreasing sequence of gaps ending at 1 (e.g. Knuth: 1, 4, 13, 40, …). For each gap, run insertion sort on the subarrays formed by elements gap apart. Larger gaps move elements long distances early; the final gap-1 pass cleans up. With Sedgewick's gaps the worst case drops to O(n^(4/3)).
def shell_sort(arr):
"""In-place Shell sort using Knuth's gap sequence."""
n = len(arr)
gap = 1
while gap < n // 3:
gap = 3 * gap + 1
while gap > 0:
for i in range(gap, n):
x = arr[i]
j = i
while j >= gap and arr[j - gap] > x:
arr[j] = arr[j - gap]
j -= gap
arr[j] = x
gap //= 3
return arr
print(shell_sort([3, 6, 1, 8, 2, 9, 4])) # [1, 2, 3, 4, 6, 8, 9]