ZetCode

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.

PropertyValue
Best case timeO(n log n)
Worst case timedepends on the gaps: O(n2) for n/2k, O(n3/2) for 3h+1
Extra spaceO(1), sorts in place
Stableno

Shell sort example

The following implementation uses Shell's original gaps: half of the list length, halved in each step.

shell_sort.py
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.

shell_trace.py
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.

gap_sequences.py
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.

bad_input.py
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.

unstable.py
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.

shell_key.py
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.

benchmark.py
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

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all Python tutorials.