Shell Sort Visualizer

How it works

1. Pick a gap. This visualizer uses Shell's original sequence: start at gap = ⌊n/2⌋ and halve it after every pass.
2. For every i from gap to n − 1, lift out tmp = A[i].
3. While j ≥ gap and A[j − gap] > tmp, shift A[j − gap] a whole gap to the right and move j back by gap.
4. Write tmp into the hole at A[j]. Every interleaved sub-sequence A[r], A[r + gap], A[r + 2·gap], … is now sorted.
5. Halve the gap and repeat. The final pass with gap 1 is plain insertion sort and guarantees a sorted array.

Worked example: sorting [62, 83, 18, 53, 7, 17, 95, 86, 47, 69]

The visualizer above opens on this 10-element array, so the gaps are 5, 2 and 1.

• Gap 5 sorts five pairs that are 5 apart: (62, 17), (83, 95), (18, 86), (53, 47) and (7, 69). Two pairs are out of order, so 17 and 47 jump five places left in a single move: [17, 83, 18, 47, 7, 62, 95, 86, 53, 69].
• Gap 2 sorts the even positions (17, 18, 7, 95, 53 → 7, 17, 18, 53, 95) and the odd positions (83, 47, 62, 86, 69 → 47, 62, 69, 83, 86) independently: [7, 47, 17, 62, 18, 69, 53, 83, 95, 86].
• Gap 1 is insertion sort on that almost-sorted array and finishes the job: [7, 17, 18, 47, 53, 62, 69, 83, 86, 95].

The visualizer counts 15 shifts in total, against 21 for plain insertion sort on the same input. On an array this small shell sort actually makes a few more comparisons (33 against 28) — the savings appear and grow quickly as n gets larger.

Why the gaps help

Insertion sort is slow because each shift moves an element one position and fixes exactly one inversion. A shift across a gap of h moves an element h positions at once and can remove many inversions with a single write. The large gaps do the coarse work cheaply; by the time the gap is 1, every element is close to its final position, which is exactly where insertion sort is at its best.

Earlier passes are never undone: an array that is h-sorted stays h-sorted after you sort it with a smaller gap. So the work of every pass accumulates.

Gap sequences and complexity

Shell sort's speed depends almost entirely on the gaps:

• Shell, 1959: n/2, n/4, …, 1 — used here because it is easy to follow. Worst case Θ(n²): when n is a power of two every gap except the last is even, so values in odd and even positions are never compared until the final pass.
• Hibbard: 1, 3, 7, 15, … (2^k − 1) — worst case O(n^1.5).
• Knuth: 1, 4, 13, 40, … ((3^k − 1)/2) — O(n^1.5), simple and popular.
• Pratt: all numbers 2^p·3^q (1, 2, 3, 4, 6, 8, 9, 12, …) — O(n log² n), but with many passes.
• Ciura, 2001: 1, 4, 10, 23, 57, 132, 301, 701 — found by experiment and the fastest known in practice.

No known gap sequence gives O(n log n) in the worst case, and the average-case complexity is still an open problem for most sequences — which is why the table below gives a range.

Stability and memory

Shell sort is in-place: it needs only tmp, i, j and gap, and no recursion. That small, stack-free footprint is why some C libraries for embedded systems (uClibc, for example) implement qsort with it.

It is not stable. Elements in different sub-sequences move independently, so a long jump can carry one copy of a value past another. With [2a, 2b, 1, 3], the gap-2 pass swaps 2a with 1, giving [1, 2b, 2a, 3], and the final pass never swaps equal values back.

When to use shell sort

Choose shell sort when you need something much faster than insertion sort on medium-sized arrays — hundreds to a few thousand elements — with tiny code, no recursion and no extra memory. For large general-purpose sorting, quick sort, merge sort or your language's library sort will be faster, and if you need stability use merge sort or insertion sort.

In interviews, be ready to explain why the last gap must be 1 (otherwise some pairs of elements are never compared) and why shell sort is not stable.

Time and space complexity

Shell Sort in Python

def shell_sort(A):
    # Sorts list A in place, ascending. NOT stable, O(1) extra space.
    # Shell's gaps n/2, n/4, ..., 1 (the last pass is insertion sort).
    n = len(A)
    gap = n // 2
    while gap > 0:
        # insertion sort on elements that are gap apart
        for i in range(gap, n):
            tmp = A[i]
            j = i
            while j >= gap and A[j - gap] > tmp:
                A[j] = A[j - gap]       # shift by a whole gap
                j -= gap
            A[j] = tmp
        gap //= 2

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Insertion Sort VisualizerInsertion sort takes each element and slides it left into place in the sorted prefix. Watch every shift animated, with Python code and O(n²) complexity.
• Quick Sort VisualizerQuick sort picks a pivot, moves smaller values left and larger ones right, then recurses: O(n log n) on average. Watch Lomuto and Hoare partitioning animated.
• Merge Sort VisualizerMerge sort splits the array in half, sorts each half recursively and merges the sorted halves, in O(n log n) time. Watch every split and merge animated.
• Bubble Sort VisualizerBubble sort repeatedly swaps adjacent out-of-order elements until a pass makes no swaps. Watch it step by step, with Python code and O(n²) complexity explained.
• Sorting Algorithm VisualizerSorting algorithm visualizer: watch bubble, selection, insertion, shell, counting, radix, merge and quick sort step by step, then race them in Compare mode.