42
0
17
1
88
2
33
3
71
4
9
5
56
6
25
7
64
8
12
9
AlgoPlus//sorting / shell sort
Read the theory

Shell Sort · Gapped Insertion

Insertion sort over shrinking gaps, then a final gap of 1.

Stability
Unstable
In-Place
Yes
Space Complexity
O(1)
Avg Time
O(n^1.25)
Size10
Legend
Comparing
Swapping / moving
Tracked (min / key)
Pivot
Sorted / found
Out of focus
AI Tutor Workspace
—
In a nutshell
Shell sort is insertion sort with a head start. Instead of only comparing neighbours, it first compares and sorts items a fixed gap apart, then repeats with smaller and smaller gaps. Big early gaps shove out-of-place values across long distances quickly, so by the time the gap shrinks to 1 the list is nearly sorted and the final pass is fast.
Ready
Press play to begin the cinematic walkthrough.
Insertion sort, but first compare items that are far apart. A large gap moves a stray value most of the way home in one hop; shrinking the gap to 1 finishes off an already nearly-sorted array.
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for Shell Sort · Gapped Insertion.