Python shell sort
last modified November 18, 2026 Python 3.15
In this article we explain the shell sort algorithm in Python. We implement
and trace it, compare different gap sequences, show an input that defeats
the original sequence, and measure the algorithm against insertion sort and
sorted.
Shell sort was published by Donald Shell in 1959. It is a generalization of insertion sort. Insertion sort moves elements only one position at a time, so an element far from its final place needs many steps. Shell sort first moves elements over long distances and gradually reduces the distance.
Shell sort algorithm
Shell sort uses a decreasing sequence of gaps ending with 1. For
each gap h, it runs insertion sort on the elements that are
h positions apart. After such a pass, the list is
h-sorted: every chain of elements taken with step h
is sorted. The final pass with gap 1 is a plain insertion sort, but by then
the list is nearly sorted, which is the best case for insertion sort.
| Property | Value |
|---|---|
| Best case time | O(n log n) |
| Worst case time | depends on the gaps: O(n2) for n/2k, O(n3/2) for 3h+1 |
| Extra space | O(1), sorts in place |
| Stable | no |
Shell sort example
The following implementation uses Shell's original gaps: half of the list length, halved in each step.
def shell_sort(vals):
gap = len(vals) // 2
while gap > 0:
for i in range(gap, len(vals)):
item = vals[i]
j = i
while j >= gap and vals[j - gap] > item:
vals[j] = vals[j - gap]
j -= gap
vals[j] = item
gap //= 2
nums = [23, 12, 1, 8, 34, 54, 2, 3]
shell_sort(nums)
print(nums)
The inner part is insertion sort in which the step 1 is replaced by
gap. Instead of sorting each chain separately, the
for loop walks the list once and inserts every element into its
own chain; the chains are interleaved.
$ python shell_sort.py [1, 2, 3, 8, 12, 23, 34, 54]
Tracing the gaps
We print the list after each gap pass together with the chains that the pass has sorted.
def shell_sort(vals):
print(f'start: {vals}')
gap = len(vals) // 2
while gap > 0:
for i in range(gap, len(vals)):
item = vals[i]
j = i
while j >= gap and vals[j - gap] > item:
vals[j] = vals[j - gap]
j -= gap
vals[j] = item
print(f'gap {gap}: {vals}')
for start in range(gap):
if gap > 1:
print(f' chain {start}: {vals[start::gap]}')
gap //= 2
shell_sort([35, 33, 42, 10, 14, 19, 27, 44, 26, 31])
With ten elements, the gaps are 5, 2, and 1. After the first pass each pair of elements five positions apart is in order. After the second pass, the even and odd positions form two sorted chains. The list is nearly sorted before the last pass, which only has to fix a few neighbours.
$ python shell_trace.py start: [35, 33, 42, 10, 14, 19, 27, 44, 26, 31] gap 5: [19, 27, 42, 10, 14, 35, 33, 44, 26, 31] chain 0: [19, 35] chain 1: [27, 33] chain 2: [42, 44] chain 3: [10, 26] chain 4: [14, 31] gap 2: [14, 10, 19, 27, 26, 31, 33, 35, 42, 44] chain 0: [14, 19, 26, 33, 42] chain 1: [10, 27, 31, 35, 44] gap 1: [10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
Gap sequences
The performance of shell sort depends on the gap sequence. Besides Shell's
n/2k, we try Knuth's sequence 1, 4, 13, 40, ... (each gap is
3h + 1) and Ciura's experimentally found sequence 1, 4, 10, 23,
57, 132, 301, 701, 1750, extended by a factor of 2.25.
import random
def shell_gaps(n):
gap = n // 2
while gap > 0:
yield gap
gap //= 2
def knuth_gaps(n):
gaps = [1]
while gaps[-1] * 3 + 1 < n // 3 + 1:
gaps.append(gaps[-1] * 3 + 1)
return reversed(gaps)
def ciura_gaps(n):
gaps = [1, 4, 10, 23, 57, 132, 301, 701, 1750]
while gaps[-1] * 2.25 < n:
gaps.append(int(gaps[-1] * 2.25))
return reversed([g for g in gaps if g < n])
def shell_sort(vals, gaps):
comparisons = 0
for gap in gaps:
for i in range(gap, len(vals)):
item = vals[i]
j = i
while j >= gap:
comparisons += 1
if vals[j - gap] <= item:
break
vals[j] = vals[j - gap]
j -= gap
vals[j] = item
return comparisons
def insertion_sort(vals):
return shell_sort(vals, [1])
rng = random.Random(21)
n = 10_000
data = rng.sample(range(n), n)
print(f'Knuth gaps: {list(knuth_gaps(n))}')
print(f'Ciura gaps: {list(ciura_gaps(n))}')
print()
for name, gaps in [('Shell n/2^k', shell_gaps(n)), ('Knuth 3h+1', knuth_gaps(n)),
('Ciura', ciura_gaps(n))]:
vals = data.copy()
count = shell_sort(vals, gaps)
assert vals == sorted(data)
print(f'{name:<12} {count:>12,} comparisons')
print(f'{"insertion":<12} {insertion_sort(data.copy()):>12,} comparisons')
We count comparisons for sorting the same 10,000 random numbers. All gap sequences need about 200,000 comparisons, while plain insertion sort, which is shell sort with the single gap 1, needs almost 25 million. Ciura's sequence is the best of the three; it is considered one of the best known sequences in practice.
$ python gap_sequences.py Knuth gaps: [3280, 1093, 364, 121, 40, 13, 4, 1] Ciura gaps: [8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1] Shell n/2^k 260,546 comparisons Knuth 3h+1 230,875 comparisons Ciura 190,037 comparisons insertion 24,862,888 comparisons
A bad input for Shell's gaps
When n is a power of two, all of Shell's gaps except the last one are even. Elements at even and odd positions are then never compared with each other until the final pass.
def shell_gaps(n):
gap = n // 2
while gap > 0:
yield gap
gap //= 2
def knuth_gaps(n):
gaps = [1]
while gaps[-1] * 3 + 1 < n // 3 + 1:
gaps.append(gaps[-1] * 3 + 1)
return reversed(gaps)
def shell_sort(vals, gaps):
comparisons = 0
for gap in gaps:
for i in range(gap, len(vals)):
item = vals[i]
j = i
while j >= gap:
comparisons += 1
if vals[j - gap] <= item:
break
vals[j] = vals[j - gap]
j -= gap
vals[j] = item
return comparisons
n = 4096
half = n // 2
data = [x for pair in zip(range(half, n), range(half)) for x in pair]
print(data[:8], '...')
for name, gaps in [('Shell n/2^k', shell_gaps), ('Knuth 3h+1', knuth_gaps)]:
vals = data.copy()
count = shell_sort(vals, gaps(n))
print(f'{name:<12} {count:>10,} comparisons')
We interleave the large half of the numbers at even positions with the small half at odd positions. The passes with even gaps leave the list unchanged, and the final insertion sort has to move every small number a long way. The original sequence needs over two million comparisons, close to the quadratic worst case. Knuth's gaps are not all even, so they handle this input easily.
$ python bad_input.py [2048, 0, 2049, 1, 2050, 2, 2051, 3] ... Shell n/2^k 2,143,232 comparisons Knuth 3h+1 44,720 comparisons
Shell sort is not stable
The long-distance moves can carry an element past an equal one in another chain.
def shell_sort(vals, key):
gap = len(vals) // 2
while gap > 0:
for i in range(gap, len(vals)):
item = vals[i]
j = i
while j >= gap and key(vals[j - gap]) > key(item):
vals[j] = vals[j - gap]
j -= gap
vals[j] = item
gap //= 2
cars = [('Audi', 1), ('BMW', 2), ('Skoda', 1), ('Volvo', 1)]
print(sorted(cars, key=lambda c: c[1]))
shell_sort(cars, key=lambda c: c[1])
print(cars)
We sort cars by a category number. With gap 2, Volvo is compared only with
BMW in its own chain and jumps two positions to the left, past Skoda, which
has the same key. The final pass does not swap equal elements, so Volvo
stays before Skoda. The sorted function keeps the input order
Audi, Skoda, Volvo.
$ python unstable.py
[('Audi', 1), ('Skoda', 1), ('Volvo', 1), ('BMW', 2)]
[('Audi', 1), ('Volvo', 1), ('Skoda', 1), ('BMW', 2)]
Key functions and descending order
We add the key and reverse parameters and use
Knuth's gap sequence.
def shell_sort(vals, key=None, reverse=False):
if key is None:
key = lambda e: e
keys = [key(v) for v in vals]
gaps = [1]
while gaps[-1] * 3 + 1 < len(vals):
gaps.append(gaps[-1] * 3 + 1)
for gap in reversed(gaps):
for i in range(gap, len(vals)):
item, k = vals[i], keys[i]
j = i
while j >= gap and ((keys[j - gap] < k) if reverse
else (keys[j - gap] > k)):
vals[j], keys[j] = vals[j - gap], keys[j - gap]
j -= gap
vals[j], keys[j] = item, k
words = ['zebra', 'Apple', 'mango', 'banana', 'Cherry', 'kiwi', 'date',
'fig', 'Grape', 'lemon']
shell_sort(words, key=str.casefold)
print(words)
shell_sort(words, key=len, reverse=True)
print(words)
The keys are computed once and stored in a parallel list that is moved
together with the values, so the key function is called only n times. The
str.casefold key gives a case-insensitive order. The second
call sorts by length in descending order. The five-letter words were in
alphabetical order before, but shell sort mixes them up, because it is not
stable.
$ python shell_key.py ['Apple', 'banana', 'Cherry', 'date', 'fig', 'Grape', 'kiwi', 'lemon', 'mango', 'zebra'] ['banana', 'Cherry', 'Apple', 'lemon', 'mango', 'Grape', 'zebra', 'kiwi', 'date', 'fig']
Benchmark
We compare shell sort with Ciura's gaps, insertion sort, and
sorted.
import random
import timeit
def insertion_sort(vals):
for i in range(1, len(vals)):
item = vals[i]
j = i
while j > 0 and vals[j - 1] > item:
vals[j] = vals[j - 1]
j -= 1
vals[j] = item
def shell_sort(vals):
gaps = [1, 4, 10, 23, 57, 132, 301, 701, 1750]
while gaps[-1] * 2.25 < len(vals):
gaps.append(int(gaps[-1] * 2.25))
for gap in reversed(gaps):
for i in range(gap, len(vals)):
item = vals[i]
j = i
while j >= gap and vals[j - gap] > item:
vals[j] = vals[j - gap]
j -= gap
vals[j] = item
rng = random.Random(13)
for n in (2_000, 20_000):
data = [rng.randint(0, 1_000_000) for _ in range(n)]
tests = [('shell sort', lambda: shell_sort(data.copy())),
('sorted', lambda: sorted(data))]
if n <= 2_000:
tests.insert(0, ('insertion sort', lambda: insertion_sort(data.copy())))
for name, func in tests:
t = timeit.timeit(func, number=3) / 3
print(f'n={n:>6} {name:<15} {t:.5f} s')
On 2000 numbers, shell sort is much faster than insertion sort. Ten times
more data makes shell sort only about 10 to 20 times slower, far from the
hundredfold increase of a quadratic algorithm. Insertion sort
is skipped for the larger input. The built-in sorted is still
about ten times faster. The times vary between runs and machines.
$ python benchmark.py n= 2000 insertion sort 0.04475 s n= 2000 shell sort 0.00153 s n= 2000 sorted 0.00017 s n= 20000 shell sort 0.02333 s n= 20000 sorted 0.00225 s
Source
Sorting Techniques – Python documentation
A102549: Ciura's gap sequence – OEIS
In this article we have implemented shell sort in Python and compared several gap sequences. See also Python insertion sort, Python bubble sort, Python quick sort, and Python heap sort.
Author
List all Python tutorials.