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, so the final pass has very little left to do.
- Waiting
- Being compared
- Just moved
- In final position
Shell sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n√n)
Settings
More options
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 |
Scroll the table sideways for the rest of the columns.
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, so it is an ordinary insertion sort. It is cheap by then, because little is left out of place.
Implementation
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 values