Shell sort
mediumSort elements that are `gap` apart first, so a badly-placed value jumps most of the distance in one hop, then finish with a gap of 1 on data that is now nearly ordered. The gap sequence is the whole algorithm.
O(n log n)Average depends on the gapsWorst O(n²)Space O(1)Not stableIn placeSaved in this browser - no sign-up, nothing sent anywhere.
How shell sort works
Insertion sort's weakness is that elements move one slot per comparison - a value 20 places from home costs 20 shifts. Shell sort runs insertion sort on interleaved subsequences of elements gap apart, so a displaced value hops gap places per move. Passes with shrinking gaps do the long-distance work early, and the final gap-1 pass is plain insertion sort on nearly-ordered data.
Correctness is free: that last gap-1 pass is a complete insertion sort, so the output is always right. The earlier passes exist purely to make it cheap - they never undo each other's work, only refine it. What they buy is the collapse of insertion sort's worst case: no value is far from home when the expensive pass finally runs.
The gap sequence is the whole algorithm, and this module ships three: Shell's original n/2 halving, Knuth's 3k+1 sequence (1, 4, 13, 40) with its proven O(n^1.5) bound, and Ciura's empirically tuned 1, 4, 10, 23, 57, 132, 301, 701. Switch sequences on the same array and compare the counters - the optimal sequence is still an open problem.
Step by step
- Sort [23, 12, 1, 8, 34, 54, 2, 3] with Shell's gaps: 4, then 2, then 1.
- Gap 4 compares pairs four apart: 23-34, 12-54, and 1-2 are ordered; 8 > 3, so they trade across four slots in one hop: [23, 12, 1, 3, 34, 54, 2, 8].
- Gap 2 insertion-sorts the even and odd subsequences: 1 hops to the front, 2 crosses four slots in two hops, 8 comes forward: [1, 3, 2, 8, 23, 12, 34, 54].
- Look at that array: after two coarse passes, no value sits more than one slot from its final home.
- Gap 1 is plain insertion sort, but only 2 and 12 need to move, one slot each: [1, 2, 3, 8, 12, 23, 34, 54].
- The pass that dominates plain insertion sort - gap 1 - did almost nothing, because the long moves were already paid for at gaps 4 and 2.
Complexity
| Best case time | O(n log n) |
|---|---|
| Average time | depends on the gaps |
| Worst case time | O(n²) |
| Space | O(1) |
Knuth's 3k+1 sequence gives O(n^1.5); the optimal sequence is unknown.
Reference implementation
Python
def shell_sort(a):
n = len(a)
gap = n // 2
while gap > 0:
for i in range(gap, n):
key, j = a[i], i
while j >= gap and a[j - gap] > key:
a[j] = a[j - gap]
j -= gap
a[j] = key
gap //= 2
return aJavaScript
function shellSort(a) {
const n = a.length;
for (let gap = n >> 1; gap > 0; gap >>= 1) {
for (let i = gap; i < n; i++) {
const key = a[i];
let j = i;
while (j >= gap && a[j - gap] > key) { a[j] = a[j - gap]; j -= gap; }
a[j] = key;
}
}
return a;
}Worth noticing
It is insertion sort that can move things a long way
Insertion sort only ever swaps neighbours, so an element that belongs 20 places left needs 20 moves. Shell sort first sorts elements that are `gap` apart, letting a value jump most of the distance in one step, and finishes with gap = 1 - a plain insertion sort on data that is now nearly ordered.
The gap sequence is the whole algorithm
Switch between the three sequences on the same array and watch the comparison count. Shell's original n/2 halving is still O(n²) in the worst case; Knuth's 3k+1 gets you O(n^1.5). Nobody has proved the optimal sequence.
Common pitfalls
- Ending on a gap other than 1. Only the gap-1 pass guarantees a fully sorted array; every valid sequence must finish there.
- Comparing a[j] with a[j - 1] instead of a[j - gap] in the inner loop - the code quietly degenerates into repeated full insertion sorts and the gaps buy nothing.
- Trusting Shell's n/2 sequence: even gaps keep even and odd positions from ever interacting until gap 1, and crafted inputs stay O(n²). Knuth's 3k+1 exists to break that pattern.
- Expecting stability. Gap-distance hops carry values over equal elements they are never compared with - shell sort is unstable even though its gap-1 parent is stable.
- Quoting one complexity for shell sort. The bound is a property of the gap sequence: n/2 halving is O(n²) worst case, Knuth's is O(n^1.5), and better sequences are only known empirically.
Where it is used
- Embedded and libc code where O(1) space and zero recursion matter - uClibc implements qsort with shell sort.
- bzip2 uses a shell sort variant inside its block-sorting fallback path.
- Medium arrays of a few thousand elements where tiny code size beats asymptotic elegance.
- The interview discussion of improving insertion sort, plus genuine open-problem trivia: nobody knows the optimal gaps.
Frequently asked questions
What is the time and space complexity of shell sort?
It depends on the gap sequence: best case O(n log n), worst case O(n²) with Shell's original n/2 halving, and O(n^1.5) with Knuth's 3k+1 sequence - the true average for good sequences is unknown. Space is O(1); it shifts in place like insertion sort.
What is the best gap sequence for shell sort?
Nobody has proved one optimal. Ciura's sequence 1, 4, 10, 23, 57, 132, 301, 701 is the empirical front-runner; Knuth's 3k+1 has the clean proven O(n^1.5) bound; Shell's n/2 halving is the simplest and the weakest. This visualizer lets you race all three on the same input.
Is shell sort stable?
No. A gap pass can carry a value many slots in one hop, straight over an equal element in between that it never compares against. Plain insertion sort is stable precisely because moves are adjacent; shell sort trades that away for the long jumps that make it fast.
Why must shell sort's last gap be 1?
Because that final pass is a full insertion sort, and it is the only step that guarantees complete order - earlier passes only sort interleaved subsequences. The point of the larger gaps is to leave the gap-1 pass nearly nothing to do, turning insertion sort's worst case into its best.