Bucket & Shell Sort

Most "fast" sorts (merge, quick, heap) work by comparing and moving elements. Two underrated relatives instead exploit structure: shell sort speeds up insertion sort by first sorting elements that are far apart, and bucket sort skips comparisons almost entirely by scattering values into ranges. This lesson animates shell sort and explains bucket sort in prose.

Intuition

Plain insertion sort has one weakness: an element only ever moves one slot per swap. If the smallest value starts at the far right, it has to crawl all the way left one step at a time — that is the O(n²) worst case.

Shell sort fixes this by letting elements take big jumps first. With gap 3, slot 5 is compared against slot 2, slot 4 against slot 1, and so on, so a stranded value can leap three positions in a single move. Each pass shrinks the gap, so by the time the gap reaches 1 the array is nearly sorted — and insertion sort is famously fast (close to O(n)) on nearly-sorted input. You pay a little extra up front to make the final pass almost free.

Bucket sort takes a different shortcut. If your values are spread roughly uniformly over a known range, you can drop each one into one of k "buckets" (sub-ranges), sort each small bucket, then read the buckets left to right. Because each bucket holds only a handful of items, the total work is close to O(n) — it sidesteps comparison sorting entirely.

Walk through it

Step through the animation on the right. The i pointer marks the element being inserted; the j-gap pointer marks the gap-apart neighbour it is compared against; the label at the top shows the current gap.

Start with gap 3. When i reaches index 3 (value 1), its gap-3 neighbour at index 0 is 8, which is bigger — so 8 shifts right into slot 3 and 1 drops into slot 0. In one move the 1 jumped three places. Index 4 (9) is already bigger than its neighbour 3, so it stays. Index 5 (2) shifts the 5 at index 2 over and settles into slot 2. After the gap-3 pass the array is [1, 3, 2, 8, 9, 5] — much closer to sorted.

Now halve the gap to 1 and run an ordinary insertion sort. Because the far-apart inversions are already gone, every element only needs a small nudge: 2 slides past 3, and 5 slides past 9 and 8. The array finishes as [1, 2, 3, 5, 8, 9], and the gap halves to 0, so we stop.

The code, line by line

def shell_sort(a):
    n = len(a)
    gap = n // 2
    while gap:
        for i in range(gap, n):
            temp = a[i]
            j = i
            while j >= gap and a[j - gap] > temp:
                a[j] = a[j - gap]
                j -= gap
            a[j] = temp
        gap //= 2
    return a

• Line 3 seeds the gap at n // 2; line 12 halves it each pass, so the gaps shrink 3 → 1 → 0 for n = 6.
• Line 5 is just insertion sort over the array, but the comparisons on line 8 look gap slots back instead of one.
• Lines 6–7 lift the element out into temp and remember its starting slot in j.
• Line 8 is the heart of it: while the gap-apart neighbour is bigger than temp, that neighbour belongs to the right.
• Lines 9–10 shift the bigger neighbour up by gap and walk j back by gap, opening a hole for temp.
• Line 11 drops temp into its resting slot once nothing gap to its left is larger.

Complexity

Shell sort runs in place (O(1) extra space) and its time depends entirely on the gap sequence. The naive halving sequence shown here is around O(n^1.5) in practice; cleverer sequences (Hibbard, Sedgewick, Ciura) push it closer to O(n log² n). Bucket sort, by contrast, is O(n + k) average time when values are uniform, but needs O(n + k) extra space for the buckets and degrades to O(n²) if everything lands in one bucket.

When to use / pitfalls

Practice