Visualizer CodeViz · Algorithms, visualized

Part I · Elementary sorts · week 2

Shellsort

Insertion sort, but comparing keys h apart. Big first steps move keys most of the way home, so the final h = 1 pass has almost nothing left to do.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

compares (3x+1)O(n^3/2) worst case
in placeyes, no extra array
stableno
used inembedded / small code footprint

Reference: Sedgewick & Wayne, §2.1; Shell 1959.

Shellsort in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def shell_sort(a):
    n = len(a)
    h = 1
    while h < n // 3:
        h = 3 * h + 1                     # 1, 4, 13, 40, 121, 364, ...
    while h >= 1:
        for i in range(h, n):             # insertion-sort the h-subsequences
            j = i
            while j >= h and a[j] < a[j - h]:
                a[j], a[j - h] = a[j - h], a[j]
                j -= h
        h //= 3                           # then a finer pass
    return a

Why it works

What h-sorting means

An array is h-sorted when every hth element, starting anywhere, is in order — it is h interleaved sorted subsequences. Shellsort h-sorts for a decreasing sequence of h, ending at h = 1, which is plain insertion sort. The final pass is therefore guaranteed correct; the earlier passes exist only to make it cheap.

Why the early passes pay off

Two facts combine. An h-sorted array stays h-sorted when you g-sort it for g < h — progress is never undone. And insertion sort is fast on nearly-ordered input. So each pass leaves less disorder for the next, and the expensive h = 1 pass runs on an array that is already almost sorted.

The increment sequence is the open problem

Shell's original powers of two are bad (odd and even positions never compare until the end). The course uses 3x+1 (1, 4, 13, 40, …): easy to compute, and O(n3/2) in the worst case. Sedgewick's own sequence does better in practice. The best sequence, and the true average-case cost, are still unknown — a rare open problem hiding inside a nine-line function.

Why anyone still uses it

  • Tiny code, no recursion, no extra array — ideal for embedded systems, bootloaders and hardware.
  • Subquadratic on real inputs, unlike insertion or selection sort.
  • Faster than n log n sorts for small n, which is why it appears inside them as the cutoff strategy.

What to try in the animation

Watch the reverse sorted preset: insertion sort needs 45 exchanges on 10 keys, shellsort far fewer, because the h = 4 pass moves keys four positions at a time.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Shellsort in the player →

The rest of Elementary sorts