Shell Sort — Gap Sequences and Their Impact

How Shell Sort Works

Shell Sort is a generalization of Insertion Sort that allows the exchange of items that are far apart. It starts by sorting elements that are a certain gap apart, then progressively reduces the gap until it becomes 1 (at which point it becomes a standard Insertion Sort on a nearly sorted array).

The Algorithm

function shellSort(arr):
  n = length(arr)
  gap = floor(n / 2)
  while gap > 0:
    for i = gap to n-1:
      temp = arr[i]
      j = i
      while j >= gap and arr[j - gap] > temp:
        arr[j] = arr[j - gap]
        j -= gap
      arr[j] = temp
    gap = floor(gap / 2)

Why Gaps Matter

The key insight is that when the final gap-1 pass runs, the array is already nearly sorted due to previous passes with larger gaps. Since Insertion Sort runs in O(n + d) time where d is the number of inversions, and earlier passes significantly reduce inversions, the total work is much less than O(n²).

Gap Sequence Comparison

Sequence	Values	Worst-case Complexity
Shell (1959)	n/2, n/4, ..., 1	O(n²)
Hibbard (1963)	2ᵏ - 1: 1, 3, 7, 15, ...	O(n^(3/2))
Sedgewick (1986)	1, 5, 19, 41, 109, ...	O(n^(4/3))
Ciura (2001)	1, 4, 10, 23, 57, 132, 301, 701	Best known empirically
Tokuda (1992)	Ceil((9ᵏ - 4ᵏ)/(5*4ᵏ⁻¹))	O(n^(4/3)) conjectured

Ciura Gap Sequence

Ciura's sequence [1, 4, 10, 23, 57, 132, 301, 701] was found through extensive empirical testing and produces the fewest comparisons for practical array sizes. For larger arrays, the sequence is extended using the formula gap[k] = 2.25 * gap[k-1].

Properties

• Not stable: Elements can be moved past equal elements during gap passes
• In-place: O(1) extra space
• Adaptive: Benefits from partially sorted input
• No proven optimal gap sequence: The best gap sequence remains an open problem in computer science