Algorithm Guidecomplexity: O(n log² n)

Shell Sort

A generalization of insertion sort that repeats gapped insertion while progressively shrinking the gap, moving distant elements efficiently. Performance hinges on the gap sequence.

01Shell Sort

Explore How It Works

Starting shell sort. Swap far-apart values first to clear the coarse disorder, then shrink the gap and refine.

Start with a gap of 4. Pair up values four slots apart and sort each of the four pairs.

The first two pairs are 45 · 67 and 12 · 23 — the smaller one already comes first.

The third pair is 89 · 56, which is reversed. Swap them across the four-slot gap.

The fourth pair, 34 · 10, is reversed too. Move 10 forward to finish the gap-4 pass.

The gap-4 pass is done and the small values have travelled a long way forward. Now shrink the gap to 2.

With a gap of 2 the values form two groups of every other slot. Insertion-sort each group.

In the group starting at the second slot, 12 and 10 are reversed. Swap them across the two-slot gap.

The gap-2 pass is done and the array is fairly tidy. Finally shrink the gap to 1.

A gap of 1 is a plain insertion sort. Move 10 and 12, both smaller than 45, to the front.

Slot 23 into place. The array is nearly sorted already, so nothing travels far.

Finally slide 34 into the fourth slot and every value has found its place.

Shell sort is done. The coarse tidying up front left almost nothing to move in the final pass.

Live Python

1def shell_sort(arr):

# n: 8

2 n = len(arr)

# gap: 4

3 gap = n // 2

4 while gap > 0:

5 for i in range(gap, n):

6 temp = arr[i]

7 j = i

8 while j >= gap and arr[j - gap] > temp:

9 arr[j] = arr[j - gap]

10 j -= gap

11 arr[j] = temp

12 gap //= 2

13 return arr

1 / 13

02 Understand It Simply

For Everyone

🔑How It Works

Orders values that are far apart first, then narrows the gap. This gets past insertion sort's limit of moving a value one slot at a time.

💡In Plain Words

Sorts elements spaced by a gap first, then reduces the gap to finish.

A big improvement over plain insertion sort.

📍Where It's Used

–Medium-sized data
–memory-constrained environments

03 Python Implementation

A clean, readable reference implementation of the core logic of Shell Sort.

core_implementation.py

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

04 Frequently Asked Questions

FAQ

What is Shell Sort?+

A generalization of insertion sort that repeats gapped insertion while progressively shrinking the gap, moving distant elements efficiently. Performance hinges on the gap sequence.

What is the time complexity of Shell Sort?+

The time complexity of Shell Sort is O(n log² n). Follow the step-by-step visualization to see exactly why.

Where is Shell Sort used?+

Medium-sized data, memory-constrained environments.

What's a simple analogy for Shell Sort?+

Orders values that are far apart first, then narrows the gap. This gets past insertion sort's limit of moving a value one slot at a time.

→ Sorting — see allRelated