Skip to content

level 3 · Sorting

Shell Sort

Insertion sort, but values are allowed to leap instead of crawl.

9 min 75 XP

what is it

Start here

Insertion sort has one crippling flaw. If the smallest value happens to be sitting at the very end, it has to crawl left one place at a time — every single step a separate swap. That crawl is where the n² comes from.

Shell sort's fix is almost cheeky: let values move far. Instead of comparing neighbours, start by comparing values that are a big gap apart — say 4 positions. A stranded small value can now leap 4 places in one swap. Then halve the gap and do it again. And again. Until the gap is 1.

That final gap-of-1 pass *is* an ordinary insertion sort. But by then the list is nearly sorted — and 'nearly sorted' is insertion sort's best case, where it barely does any work. Shell sort's whole trick is to spend a little effort making insertion sort's job easy.

It is a rare thing in computer science: nobody knows its exact complexity. It depends on the sequence of gaps you choose, and finding the best sequence is still an open problem.

real-life analogy

Picture it

Tidying a room in passes

You don't put every single object in its exact place on the first pass. First you do a rough sweep — everything roughly toward the right side of the room. Then a finer pass. Then a final tidy-up, which is quick because almost everything is already close to where it belongs.

interactive visualization

Watch it run

Watch the gap shrink: 4, then 2, then 1. Values leap, then settle.

  1. 9
  2. 8
  3. 3
  4. 7
  5. 5
  6. 6
  7. 4
  8. 1

Shell sort is insertion sort that stops crawling. It compares values far apart first, so a small value stuck at the end can leap most of the way home in a single move.

step 01/38

  • comparing
  • moving
  • in final place
1function shellSort(a) {
2 const n = a.length;
3 for (let gap = n >> 1; gap > 0; gap >>= 1) {
4 for (let i = gap; i < n; i++) {
5 let j = i;
6 while (j >= gap && a[j - gap] > a[j]) {
7 [a[j - gap], a[j]] = [a[j], a[j - gap]];
8 j -= gap;
9 }
10 }
11 }
12 return a;
13}

variables right now

Nothing in play yet — press play.

comparisons 0moves 0

the dry run · every step, in words

38 steps

complexity

What it costs

best case
O(n log n)
average
≈ O(n^1.3)
worst case
O(n²)
extra memory
O(1)

Genuinely hard to pin down — the complexity depends on the gap sequence, and the optimal sequence is still an open research problem. With halving gaps it lands around n^1.5 in practice: far better than insertion sort, not as good as merge sort.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²) · this one
input size →work →

common mistakes

Common traps

  • Forgetting the final gap-of-1 pass.

    Without it the list is not sorted — only the gapped groups are. The last pass is what actually finishes the job.

  • Comparing a[i] with a[i-1] inside a gapped pass.

    Within a pass of gap g, you compare a[j] with a[j-g], not a[j-1]. Mixing that up turns it straight back into insertion sort.

  • Assuming any gap sequence is as good as any other.

    It matters a lot. Halving is simple but not optimal; sequences like Ciura's are measurably faster. This is one of the few algorithms where the constant really is the research.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+75 XP

01What problem with insertion sort does shell sort exist to fix?

02What is the last pass of shell sort?

03What is unusual about shell sort's time complexity?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.