SortingAlgorithmaka Shell's method, diminishing increment sort

Shell Sort

Insertion sort over elements h apart with a shrinking gap sequence, finishing with a plain insertion sort.

▶ VisualizePattern: Two Pointers
Progress

Overview

Shell sort generalizes Insertion Sort: instead of moving elements one slot at a time, it first sorts elements that are h positions apart (an "h-sort"), then repeats with smaller and smaller h, ending with h = 1. Early passes with large gaps move far-away elements long distances cheaply; the final h = 1 pass is a regular insertion sort on an array that is already nearly sorted.

Its running time depends on the gap sequence: Shell's original n/2, n/4, … gives O(n²) worst case; Knuth's (3^k - 1)/2 gives O(n^1.5); Sedgewick's sequences reach O(n^{4/3}); Ciura's empirical sequence 1, 4, 10, 23, 57, 132, 301, 701, … is fastest in practice. It is in-place, not stable, and adaptive. It is used where code size matters (embedded systems, the Linux kernel's early sort(), uClibc qsort) because it is short, needs no recursion or extra memory, and is decent for n in the thousands.

comparisonin-placeunstablegap sequencesub-quadraticadaptive

Intuition

A mental model before the formal terms.

Insertion sort is slow because a small element at the far right shuffles left one step at a time. Shell sort lets elements take big strides first: sort every 5th element among themselves, so wildly misplaced items jump across the array in a few moves. Then stride 2, then stride 1 — by then nothing has far to go.

How it works

  1. Choose a gap sequence ending in 1, e.g. Ciura's [701, 301, 132, 57, 23, 10, 4, 1] (extended by ×2.25 for large n), using only gaps < n.
  2. For each gap h: for i = h … n - 1, insertion-sort a[i] into the subsequence …, a[i - 2h], a[i - h] by shifting elements h apart while they are larger.
  3. Each gap pass leaves the array h-sorted; a key property is that an array that is h-sorted stays h-sorted after being g-sorted.
  4. The final h = 1 pass is plain insertion sort and guarantees correctness.

Why it works

Correctness is trivial: the last pass is insertion sort, which always sorts. The earlier passes are only an optimization.

Efficiency: after h-sorting, the number of inversions left is greatly reduced; insertion sort runs in O(n + I), so later passes are cheap. The h-sortedness preservation property means the work of large gaps is not undone.

The exact bound depends on the gap sequence and is an open problem in general; good sequences avoid gaps sharing common factors so that subsequences interleave.

Recognition

How to tell a problem wants this.

  • A sub-quadratic sort with tiny code, no recursion, and O(1) space is required (embedded, bootloaders, interpreters).
  • Explicitly asked about gap sequences or how to improve insertion sort.
  • Moderate n (a few thousand) where O(n^1.3) in practice is fine and library sorts are unavailable.
“sorted array” → Two Pointers

Interactive visualization

Play, step, change the input. ← → and space work too.

29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/51Start with gap = 4. Shell sort runs insertion sort on elements gap apart, so far-away elements move in one hop instead of many adjacent swaps.
Key being insertedElement gap positions leftShifted right by gapSorted
PseudocodeLearn Shell Sort →
1gap = n // 2
2while gap > 0:
3  for i in gap .. n-1:
4    key = a[i]; j = i
5    while j >= gap and a[j-gap] > key:
6      a[j] = a[j-gap]; j -= gap
7    a[j] = key
8  gap = gap // 2
Variables
gap4
Complexity
best O(n log n)
avg O(n^1.25)–O(n^1.5)
worst O(n^1.5)
space O(1)
Speed

Pseudocode

1for h in gaps (descending, ending with 1):
2  for i from h to n - 1:
3    key = a[i]; j = i
4    while j >= h and a[j - h] > key:
5      a[j] = a[j - h]; j -= h
6    a[j] = key

Implementations

1def shell_sort(a: list[int]) -> None:
2    n = len(a)
31 · Build the Ciura gap sequence, extended by x2.25
4    gaps = [1, 4, 10, 23, 57, 132, 301, 701]
5    while gaps[-1] * 2.25 < n:
6        gaps.append(int(gaps[-1] * 2.25))
72 · One pass per gap, largest first (skip gaps >= n)
8    for h in reversed(gaps):
9        if h >= n:
10            continue
113 · Gapped insertion sort: shift larger elements h apart
12        for i in range(h, n):
13            key = a[i]
14            j = i
15            while j >= h and a[j - h] > key:
16                a[j] = a[j - h]
17                j -= h
18            a[j] = key
Walkthrough
  1. Sorts in place and returns None, following the list.sort() convention (returning the list would suggest a copy was made).
  2. gaps[-1] * 2.25 mixes int and float; int(...) truncates back — for these magnitudes the float math is exact enough, and Python ints themselves never overflow.
  3. reversed(gaps) iterates largest gap first without copying the list.
  4. The while loop shifts elements h apart; tuple-free single assignments (a[j] = a[j - h]) do one write per shifted element.
  5. The final h = 1 pass is plain insertion sort, so correctness never depends on the earlier gaps.
Complexity (this implementation)
time O(n^1.5) worst, ~O(n^1.25) empirically · space O(1)

Pure-Python loops mean sorted() / list.sort() (TimSort in C) win by orders of magnitude at any n — shell sort in Python is for understanding, not speed.

Language notes
  • list.sort() and sorted() are stable TimSort implemented in C; there is no scenario where hand-written shell sort beats them in CPython.
  • reversed(gaps) returns a lazy iterator; gaps[::-1] would copy the list.
  • For NumPy arrays, np.sort(kind="stable") or kind="quicksort" (introsort) are the vectorized answers; element-wise Python loops over ndarrays are slower still.
Common mistakes in this language
  • Halving gaps with h //= 2 from n — the classic O(n²) sequence.
  • Writing while j >= 0 and a[j - h] > key — negative indices wrap in Python, so this silently compares against the array tail instead of raising.
  • Expecting stability from shell sort when replacing a sorted(key=...) call — equal keys can reorder.
Language differences that matter here
  • Gap arithmetic: C++ extends the sequence with integer math (* 9LL / 4) to avoid float rounding and int overflow; JS/TS and Python use 2.25 directly — safe because JS numbers are exact integers below 2^53 and Python ints are unbounded.
  • Negative index guard: j >= h protects a[j - h] in every language, but the failure mode differs — C++ is undefined behaviour, JS reads undefined (comparison false, silently "works"), Python wraps around to the tail and corrupts the sort.
  • None of the four standard libraries uses shell sort: C++ std::sort is introsort, Python sorted() and V8's Array.prototype.sort are TimSort — shell sort survives where code size and O(1) space matter (embedded, bootloaders).
  • In-place mutation style: C++ takes std::vector<int>&, JS/TS mutate and return void like Array.prototype.sort, Python returns None like list.sort().

Complexity

Best
O(n log n)
Average
O(n^1.25)–O(n^1.5)
Worst
O(n^1.5)
Space
O(1)

Depends on gap sequence: Shell n/2^k is O(n²) worst; Knuth (3^k−1)/2 is O(n^1.5); Sedgewick O(n^4/3); Ciura best empirically. In-place, not stable, adaptive.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Small-footprint environments where a recursion-free, allocation-free, sub-quadratic sort is needed.
  • Medium-sized arrays (hundreds to low tens of thousands) when a library sort is unavailable.
  • Nearly sorted data where it approaches O(n log n) behaviour.
Avoid it when
  • Large arrays — O(n log n) sorts (Merge Sort, Quick Sort, Heap Sort) win clearly.
  • Stability is required — gap passes move equal elements past each other.
  • When a provable tight bound is needed; shell sort's analysis is sequence-dependent and partly open.

Alternatives

Insertion SortHeap SortQuick SortMerge Sort

Common mistakes

  • Using gaps n/2, n/4, …, 1 — powers of two share factors and never mix even and odd positions until the last pass, giving O(n²) worst case.
  • Forgetting the final h = 1 pass, leaving the array only partially sorted.
  • Assuming stability.
  • Off-by-one in the inner loop bound j >= h (must not read a[j - h] for j < h).

Interview patterns

  • Explain why a gap of 1 must be last and why powers of two are a poor sequence.
  • Compare against Insertion Sort on nearly sorted vs random data.
  • Rarely asked to implement; usually a discussion question about improving simple sorts.
Interview questions on this
Mock interviews

Example problems

No linked problems yet.