How Shell Sort Works
Shell sort runs insertion sort on elements a gap apart, then shrinks the gap to one. The early wide passes move values most of the way home cheaply, which is what makes the final pass fast.
- Waiting
- Being compared
- Just moved
- In final position
Step 1 of 88
Shell sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n√n)
Settings
Two to 48 numbers. Sorted in exactly the order you type them.
Shell sort
- 1
gap = n / 2 - 2
while gap >= 1: - 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] - 7
j -= gap - 8
a[j] = key - 9
gap = gap / 2
The same array, every algorithm
Comparisons on the values above, cheapest first. Writes in the second line. Run it on nearly sorted values to see the O(n log n) sorts lose.
- Merge3344 writes
- Quick3340 writes
- Insertion4042 writes
- Shell4637 writes
- Heap5166 writes
- Bubble6062 writes
- Selection6618 writes
How the seven compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Stable means equal values keep their original order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n log n) | ≈O(n^1.25) | O(n²) | O(1) |
Every bound here depends on the gap sequence. These figures are for halving; Ciura's sequence does measurably better and has no closed-form proof at all.
How shell sort works
Insertion sort's weakness is that a value can only move one position per shift, so a small value at the far end has to crawl the whole way. Shell sort fixes that by first sorting elements that are a wide gap apart, letting a value jump most of the distance in one move, then repeating with smaller gaps. The final pass is a plain insertion sort on an array that is already nearly ordered — which is the case insertion sort handles best.
- Pick a starting gap — commonly half the array length.
- Run an insertion sort on each subsequence of elements that are gap apart.
- Halve the gap and repeat. Each round leaves the array closer to sorted than the last.
- The final round has a gap of 1, which is an ordinary insertion sort — now cheap, because little is left out of place.
Implementation
The same algorithm the visualiser is running, written to be read.
def shell_sort(values):
n = len(values)
gap = n // 2
while gap > 0:
# An insertion sort where neighbours are 'gap' apart.
for i in range(gap, n):
key = values[i]
j = i
while j >= gap and values[j - gap] > key:
values[j] = values[j - gap]
j -= gap
values[j] = key
gap //= 2
return valuesWhen to use it
- Use it when you need better than quadratic behaviour with no extra memory and no recursion — embedded code, kernels, bootloaders.
- Use it when the code has to stay small: it is a few lines more than insertion sort and dramatically faster on mid-sized arrays.
- Avoid it when you need a guarantee. Its complexity depends on a gap sequence chosen by experiment, and it is not stable.
Check yourself
If the animation made sense, these should too.
What problem do the wide early passes solve?
Insertion sort moves a value one position per shift, so a small value at the far right has to crawl the whole way. Sorting elements a large gap apart lets that value jump most of the distance in a single move, so by the time the gap reaches 1 there is very little left to shift.
Why does its complexity have no single agreed answer?
Because it depends entirely on the gap sequence. Halving gives an O(n²) worst case; Ciura's experimentally chosen sequence performs measurably better and has no proven bound at all. Shell sort is one of the few classic algorithms whose best-known parameters come from measurement rather than proof.