Shell Sort Explained
Shell Sort is a gap-based generalization of Insertion Sort that moves elements long distances early. Learn how gap sequences work and its time complexity.
On this page +
Shell Sort is a clever generalization of Insertion Sort. Plain Insertion Sort only moves elements one step at a time, which is slow when an element is far from home. Shell Sort fixes this by first comparing elements that are far apart, then progressively reducing the gap until it finishes with a normal Insertion Sort on nearly-sorted data.
How Shell Sort works #
Choose a sequence of decreasing gaps (for example 5, 2, 1). For each gap, perform an Insertion Sort on the subsequences of elements that are that gap apart. Large gaps move elements long distances quickly; by the time the gap reaches 1, the array is almost sorted, so the final Insertion Sort pass is nearly O(n).
The gap sequence matters #
Performance depends heavily on the gap sequence. Shell's original n/2 sequence gives O(n²) worst case; better sequences like Hibbard (2^k − 1) achieve O(n^1.5), and Sedgewick's reaches around O(n^1.3). This sensitivity to the gap schedule is what makes Shell Sort theoretically interesting.
Complexity and use #
Shell Sort is O(1) space, in-place, and not stable. Its time complexity ranges from O(n log n) to O(n²) depending on gaps. It is rarely used in libraries today but appears in embedded systems and is a great example of how a small idea dramatically improves a simple algorithm. Watch the long-distance swaps in the visualizer.
Frequently asked questions
How is Shell Sort different from Insertion Sort? +
What is the best gap sequence for Shell Sort? +
See it in motion
Watch this algorithm and nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.