Heaps & gaps · Intermediate
Shell Sort
Insertion-sort values far apart first, then reduce the gap until adjacent order remains.
- Best
- O(n log n)
- Average
- Gap-dependent
- Worst
- O(n²)
- Space
- O(1)
- Stability
- Not stable
- Memory model
- In-place
How it builds order
- Choose a large gap.
- Insertion-sort each interleaved gap group.
- Reduce the gap.
- Finish with gap 1.
Why it works
Early passes remove long-distance inversions, leaving little work for the final insertion pass.
Watch for: Large gaps move distant values quickly; gap 1 finishes with ordinary Insertion Sort.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.