Sorting Algorithm

Shell Sort

Generalizes insertion sort by first comparing elements that are far apart (a large 'gap'), moving badly-placed values a long distance in one move, then shrinking the gap until it reaches 1 — a final, now much cheaper, ordinary insertion sort. With the simple 'halve the gap' sequence shown here, worst case is still O(n²); smarter gap sequences (Hibbard, Sedgewick) improve on that, at the cost of a trickier implementation.

BestO(n log n)
Average≈O(n^1.3)
WorstO(n²)*
SpaceO(1)
StableNo

Try It — Animated Flow

29
8
44
15
3
37
21
Shell sort is insertion sort with a twist: it first compares elements far apart (a 'gap'), then shrinks the gap down to a normal insertion sort.
Step 1 / 27
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

bzip2's block-sorting step
The bzip2 compressor's original implementation used a Shell sort internally, chosen for its very small code footprint rather than for being the fastest option.
Embedded systems & bootloaders
Its O(1) space, no recursion, and short implementation make it a reasonable fallback sort where code size and stack depth matter more than optimal speed.
Bridging the gap while learning
Shell sort is a natural teaching stepping stone: it shows how a small tweak to insertion sort (comparing far-apart elements first) meaningfully improves its real-world performance.
Sorting medium-sized in-place data
For arrays too big for plain insertion sort but where allocating O(n) extra memory (like merge sort needs) isn't worth it, Shell sort is a simple middle ground.

Trade-offs

Reach for it when
  • The array is medium-sized (too big for insertion sort, not huge)
  • You want an in-place sort with a tiny, simple implementation
  • Code size / no recursion matters more than best-in-class speed
Avoid it when
  • The dataset is large — better O(n log n) sorts exist
  • Stability is required
  • You need a rigorously provable worst-case bound (use Heap Sort or Merge Sort)