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]For seven elements, the loop while gap < n // 3: gap = 3 * gap + 1 stops at gap 4 (since 4 is not below 7 // 3 = 2 once reached). The gap-4 pass runs insertion sort independently on the interleaved subsequences at indices (0, 4), (1, 5) and (2, 6), plus index 3 on its own. Only the pair (3, 2) is out of order, so 2 jumps four positions to the front in a single move. Insertion sort alone would have needed four adjacent swaps to do that. The gap then shrinks to 1 and a plain insertion sort finishes the job; because most elements are already close to their final position, the inner loop runs only a few times.
Why does this help? Insertion sort's cost is proportional to the number of inversions, pairs of elements that are out of order. An element that is far from its final position creates many inversions, and adjacent swaps remove only one inversion each. A long-distance move across a large gap can remove many inversions at once. The early passes therefore do the heavy lifting cheaply, and the final pass operates on an input with few inversions, where insertion sort is close to linear.
Shell sort is a family of algorithms: the gap sequence determines its running time. Shell's original sequence (n/2, n/4, ..., 1) has a quadratic worst case because even and odd positions do not mix until the last pass. Knuth's sequence (3h + 1) gives O(n^(3/2)) worst case and is simple to generate. Sequences from Sedgewick and later empirical work by Ciura (1, 4, 10, 23, 57, 132, 301, 701, ...) perform better in practice. No gap sequence is known to achieve O(n log n) worst case, and a tight analysis of the average case remains an open problem for most sequences.
CIURA = [701, 301, 132, 57, 23, 10, 4, 1]
def shell_sort_ciura(arr):
n = len(arr)
for gap in CIURA:
if gap >= n:
continue
for i in range(gap, n):
x, j = arr[i], i
while j >= gap and arr[j - gap] > x:
arr[j] = arr[j - gap]
j -= gap
arr[j] = x
return arr
import random
data = [random.randint(0, 999) for _ in range(500)]
assert shell_sort_ciura(data[:]) == sorted(data)For arrays larger than the last listed gap, the Ciura sequence is usually extended by multiplying by about 2.25. The inner loop is identical to insertion sort, except that it steps by gap instead of 1, which is why Shell sort is often described as "insertion sort with long jumps".
Shell sort occupies a niche between the simple quadratic sorts and the O(n log n) algorithms. It needs no recursion and no auxiliary arrays, has a tiny code footprint and performs well on medium-sized inputs, which makes it attractive for embedded systems, firmware and environments where stack depth is limited. Some C libraries historically used it for small arrays. For general-purpose sorting in a high-level language, the built-in sort (Timsort in Python, a hybrid introsort or pdqsort in many C++ libraries) is faster and stable.
| Algorithm | Worst time | Extra space | Stable |
|---|---|---|---|
| Insertion sort | O(n²) | O(1) | yes |
| Shell sort (Knuth) | O(n^(3/2)) | O(1) | no |
| Heapsort | O(n log n) | O(1) | no |
| Mergesort / Timsort | O(n log n) | O(n) | yes |