A reverse-sorted array exposes insertion sort’s movement cost. An element that belongs k positions away needs k one-slot shifts to get there. Across a fully inverted array, the total shift work equals the number of inversions.
Shell sort reduces that long-distance disorder first. It runs insertion sort over elements h positions apart, then repeats with smaller gaps until h = 1. A move within an h-spaced subsequence relocates an element by h slots at once, so coarse passes can move badly placed values much closer to their destinations. The final pass is ordinary insertion sort. How much work remains for it depends on the gap sequence.
Core condition: a decreasing gap sequence ending at h = 1 → each pass h-sorts interleaved subsequences → the final adjacent pass completes the ordering.
Visualization
The shrinking gap is the transition worth animating: after the h = 4 lanes move distant values close to their destinations, the h = 1 pass only resolves the remaining local inversions.
Why H-sorting Cuts the Shift Work
An array is h-sorted when a[i] ≤ a[i + h] for every valid i. A gap-h pass treats the array as h interleaved subsequences — indices {0, h, 2h, …}, {1, h+1, …}, and so on — and insertion-sorts each one independently. Because the stride is h, a single shift moves an element h positions rather than one.
The pass ordering is valid because the sequence ends at gap 1, which directly compares adjacent positions and completes the ordering. Earlier gaps move distant elements toward their destinations; they do not guarantee that every element is already close to its final slot before that last pass.
On the reverse-sorted [9, 8, 7, 6, 5, 4, 3, 2, 1], a gap-4 pass sorts the four subsequences {9,5,1}, {8,4}, {7,3}, {6,2} and yields [1, 4, 3, 2, 5, 8, 7, 6, 9]. The closing h = 1 pass then resolves the remaining adjacent disorder.
The algorithm is not stable: a shift jumps h positions and can carry a key past an equal key sitting between them, and no later pass restores their original relative order.
Complexity
Shell Sort complexity
Average: Around n^1.3 in measurements of Ciura-style increments
Worst: Θ(n²) with Shell's n/2, n/4, …; Θ(n^1.5) with Hibbard's 2^k − 1; O(n^4/3) with Sedgewick's
n
number of elements in the array
The bound belongs to the gap sequence, not to Shell sort alone. For power-of-two lengths, Shell’s original schedule keeps even and odd positions separate until the final pass and retains quadratic worst-case work. Hibbard and Sedgewick sequences improve the proven tail; Ciura’s tuned gaps perform well in measurements but have no tight nontrivial asymptotic bound.
There is also no way to buy a proven bound and top speed at once. Pratt’s 3-smooth gaps give a proven Θ(n log² n) worst case, but they use so many passes that constant factors make them slower in practice than Ciura’s unproven-but-fast sequence. A workload that needs a contractual O(n log n) guarantee cannot get it from Shell sort — heap sort or introsort can.
The h-stride can lift one equal key over another. Shell sort is therefore a poor fit when a secondary sort must preserve the earlier ordering of equal keys.
Diagram and C# Implementation
Pass structure
flowchart TD
A[Input array and gap sequence] --> B[Take next largest gap h]
B --> C[Insertion-sort each h-spaced subsequence]
C --> D{h equals 1}
D -->|No| E[Shrink to next smaller gap]
E --> B
D -->|Yes| Z[Array sorted]
C# implementation
public static void ShellSort(int[] a){ int n = a.Length; // Ciura's empirically tuned gaps, largest first. int[] gaps = { 701, 301, 132, 57, 23, 10, 4, 1 }; foreach (int gap in gaps) { if (gap >= n) continue; // Gapped insertion sort: h interleaved subsequences at stride `gap`. for (int i = gap; i < n; i++) { int key = a[i]; int j = i; while (j >= gap && a[j - gap] > key) { a[j] = a[j - gap]; // shift by a whole gap, not by one j -= gap; } a[j] = key; } }}
The inner loop is insertion sort with gap as its stride instead of 1. The final gap still sorts any input length, but a scalable implementation extends the sequence from n so large arrays receive useful coarse passes.