SORTING · ADVANCED

Shell sort

Run insertion sort on items far apart first, then on closer and closer items, ending with a normal insertion sort.

Time O(n²) worst case with halving gapsSpace O(1)2 practice problemsStep-through picture

The idea

Insertion sort is slow when an item has to travel far, because it moves only one spot per step. Shell sort, named after Donald Shell, fixes that by first sorting items that are a big distance apart, called the gap.

With a gap of 4, it insertion-sorts the items at positions 0, 4, 8, ... as one group, the items at 1, 5, 9, ... as another, and so on. Small items far to the right jump left four spots at a time. Then it halves the gap and does it again, until the gap is 1, which is a plain insertion sort.

By the last pass, the list is nearly sorted, so the final insertion sort has little work left. Shell sort's speed depends on the gap sequence: with simple halving it is O(n²) in the worst case, but in practice it is much faster than insertion sort.

An everyday example

Tidying a bookshelf from across the room first

A long bookshelf is badly out of order. Instead of shifting books one slot at a time, you first fix books that are far out of place, swapping books four slots apart if they are clearly in the wrong order. Then you look at books two slots apart, then at neighbors. By the time you check neighbors, almost every book is already close to its spot.

How the example maps to the code
In the example	In the code
How far apart the books you compare are	`gap`
Shrinking how far you look	`gap = Math.floor(gap / 2)`
Shifting a book along by several slots	`items[j] = items[j - gap]`
Checking neighbors at the end	The final pass with `gap = 1`

From the slow way to shell sort

Insertion sort is fast on nearly sorted lists and slow on scrambled ones. The reason is that each shift moves an item one place, so an item that is 500 places from its spot needs 500 shifts. Every shift fixes just one out-of-order pair.
What if an item could jump many places at once? Pick a distance, called the gap, say 4. Look only at the items at indexes 0, 4, 8, and so on, and insertion-sort them as their own small list. Then do the same for indexes 1, 5, 9, and the rest. Now one shift moves an item 4 places, and can fix several out-of-order pairs at once.
A list where items 4 apart are in order is not sorted yet. But it is closer: small items have moved far toward the front. Now shrink the gap, to 2, then to 1. A gap of 1 is plain insertion sort, so the final pass always produces a sorted list, and it is cheap because the earlier passes did most of the moving.
In code, the groups don't need to be handled one at a time. Walk i from gap to the end and insert items[i] into its own group by comparing with items[i - gap], items[i - 2 * gap], and so on. Do that for each gap in a shrinking sequence ending with 1: that loop is Shell sort.

How it works

Start with gap = Math.floor(items.length / 2).
For each i from gap to the end, save current = items[i].
Set j = i. While j >= gap and items[j - gap] > current, shift items[j - gap] forward to items[j] and move j back by gap.
Put current at items[j]. This is insertion sort over items gap apart.
Halve the gap and repeat. The last pass, with gap = 1, is a plain insertion sort that finishes the job.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function shellSort(items) {
for (let gap = Math.floor(items.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < items.length; i++) {
const current = items[i];
let j = i;
while (j >= gap && items[j - gap] > current) {
items[j] = items[j - gap];
j -= gap;
}
items[j] = current;
}
}
return items;
}

How fast it is

Time	`O(n²) worst case with halving gaps`
Extra memory	`O(1)`

There are about log n gap rounds, and each costs at least one look at every item. How many shifts happen depends on the gap sequence; with plain halving, a bad input can still need O(n²).

Best caseO(n log n)
An already sorted list, like [2, 4, 6, 8, 10, 12]. About log₂ n gap passes each check every item once, and nothing moves.
Average caseO(n²)
With halving gaps, no better bound is proven, though random lists are much faster in practice: in one test, 1,024 random numbers took about 17,800 shifts, versus about 262,000 for insertion sort.
Worst caseO(n²)
With halving gaps and a length that is a power of 2, even and odd indexes are never compared until gap = 1. Putting the big half at even indexes, like [9, 1, 10, 2, 11, 3, 12, 4, ...], leaves all the work, about n² / 8 shifts, to the last pass.

Common mistakes

Ending with a gap other than 1. The list is then only gap-sorted, not sorted.
Comparing items[j - 1] instead of items[j - gap], which mixes up the groups.
Expecting a stable sort; equal items can change order.
Writing gap /= 2 without Math.floor. The gap becomes a fraction like 1.5, and items[j - gap] reads non-integer indexes.

When to use it

Look for these clues in a problem:

You need an in-place sort with very little code and better speed than insertion sort on medium-sized lists.
The question asks about gapped insertion passes or the array after each gap.
Memory is tight and recursion is not wanted.

Check yourself

Answer each one in your head first, then open it.

Why must the last gap be 1?

Only the gap-1 pass compares every pair of neighbors. With a last gap of 2, the list is only sorted within its even and odd positions, not as a whole.

What is the sequence of gaps this code uses for 20 items?

10, 5, 2, 1. Each gap is Math.floor of half the previous one, and the loop stops when it reaches 0.

Why can one shift in Shell sort do more good than one shift in insertion sort?

It moves an item gap places at once, past several items that may all be out of order with it. Insertion sort's shift fixes exactly one out-of-order pair.

Why is Shell sort not stable?

Items in different gap groups move independently, so an item can jump over an equal item from another group.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

#210One Gapped Insertion Pass

medium

#209Shell Sort Gap Snapshots

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Correctness rests entirely on the last pass. When gap is 1, the inner code compares items[j - 1] with current and shifts by one, which is exactly insertion sort. Insertion sort sorts any list, whatever state the earlier passes left it in, so the result is always sorted.

Each pass with a bigger gap keeps one rule: it only rearranges items within their own group (indexes that differ by a multiple of gap), and it leaves each group sorted. It never loses or duplicates an item, because each step saves current, shifts, and writes current back once, as in insertion sort.

The earlier passes are there for speed. A shift of gap places can fix up to 2 × gap - 1 out-of-order pairs at once, not just one. There is also a useful fact: sorting with a smaller gap never undoes the order a bigger gap created. So the list keeps getting closer to sorted, and the final insertion sort has few pairs left to fix.

Every loop ends: i runs to the end of the list, j drops by gap until it is below gap, and gap halves until it reaches 0.

Going deeper

3 more ideas

Why it ends sorted

The last pass uses gap = 1, which is exactly insertion sort, and insertion sort always sorts any list. The earlier passes are only there to make that last pass cheap: they move items most of the way to their place in big jumps, so the final pass has few out-of-order pairs to fix.

Gap sequences and speed

Halving the gap (n/2, n/4, ..., 1) is the simplest choice but has a worst case of O(n²). Better sequences, such as Knuth's 1, 4, 13, 40, ... (each is 3 × previous + 1), bring the worst case down to about O(n^1.5). No sequence is known that makes Shell sort O(n log n) in the worst case.

Not stable

Items jump over others by gap positions, so two equal items in different gap groups can swap their order. If you need equal items to keep their order, use insertion sort or merge sort.

Work it by hand

Every step in a table, with why

Sort 8 numbers with gaps 4, 2, 1. Steps where nothing moves are grouped.

items = [9, 4, 12, 6, 1, 10, 3, 7]

Step	`gap`	`i`	`current`	Shifted	`items`	What happens	Why
1	4	4	1	9	[1, 4, 12, 6, 9, 10, 3, 7]	`1` jumps to index 0	`gap` starts at `Math.floor(8 / 2) = 4`. `items[0] = 9` is bigger than `1`, so `9` shifts 4 places right and `1` moves 4 places left in one step.
2	4	5	10	-	[1, 4, 12, 6, 9, 10, 3, 7]	`4 > 10` is false	`10` is already in order with `items[1]`.
3	4	6	3	12	[1, 4, 3, 6, 9, 10, 12, 7]	`3` jumps to index 2	Another long move. Plain insertion sort would need 4 shifts to move `3` this far.
4	4	7	7	-	[1, 4, 3, 6, 9, 10, 12, 7]	`6 > 7` is false	The gap-4 pass ends. Items 4 apart are now in order.
5	2	2 to 6	-	-	[1, 4, 3, 6, 9, 10, 12, 7]	No moves	`gap` becomes 2. Each of these items is already at least as big as the one 2 places back.
6	2	7	7	10	[1, 4, 3, 6, 9, 7, 12, 10]	`7` moves to index 5	`10` shifts right; then `items[3] = 6` is not bigger than `7`, so the loop stops.
7	1	1	4	-	[1, 4, 3, 6, 9, 7, 12, 10]	No move	`gap` becomes 1: this pass is plain insertion sort.
8	1	2	3	4	[1, 3, 4, 6, 9, 7, 12, 10]	`3` moves to index 1	One shift.
9	1	3 to 4	-	-	[1, 3, 4, 6, 9, 7, 12, 10]	No moves	`6` and `9` are in place.
10	1	5	7	9	[1, 3, 4, 6, 7, 9, 12, 10]	`7` moves to index 4	One shift.
11	1	6	12	-	[1, 3, 4, 6, 7, 9, 12, 10]	No move	`12` is bigger than `9`.
12	1	7	10	12	[1, 3, 4, 6, 7, 9, 10, 12]	`10` moves; loop ends	After this, `gap` becomes `Math.floor(1 / 2) = 0`, and `gap > 0` ends the outer loop.

It returns [1, 3, 4, 6, 7, 9, 10, 12] after 6 shifts. Plain insertion sort on the same list needs 16 shifts, one per out-of-order pair, because each of its shifts moves an item only one place.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Shell sort	`O(n²)`	`O(1)`	Medium lists in memory-limited code where you want a short, in-place, non-recursive sort and stability doesn't matter.
Shell sort with Knuth's gaps	`O(n^1.5)`	`O(1)`	Same uses, with a better proven worst case. Only the gap sequence changes.
Insertion sort	`O(n²)`	`O(1)`	Small or nearly sorted lists, or when you need stability.
Heap sort	`O(n log n)`	`O(1)`	You need a guaranteed `O(n log n)` in place on large lists.

Extra memory: O(1): just gap, i, j, and current. It sorts in place with no recursion.

How the steps grow

Shell sort, Insertion sort O(n²)
Shell sort with Knuth's gaps O(n^1.5)
Heap sort O(n log n)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Shell sort	100	1 million	1 trillion
Shell sort with Knuth's gaps	32	31,623	1 billion
Insertion sort	100	1 million	1 trillion
Heap sort	33	9,966	20 million

Inputs that need care

5 tricky inputs

An empty list or one item: Math.floor(n / 2) is 0, so gap > 0 is false and nothing runs.
Two items: [8, 3]: The first gap is 1, so it is just one insertion step: 3 shifts 8 right and the result is [3, 8].
Already sorted: Every items[j - gap] > current check fails at once. It costs one comparison per item per gap, about n × log₂ n in total.
The interleaved bad case: 1,024 items with the big half at even indexes: All 131,328 shifts happen in the final gap = 1 pass, exactly as many as plain insertion sort. A better gap sequence, which mixes even and odd gaps, avoids this.
Equal items with labels: [1, 2a, 2b, 0]: With gap = 2, 0 jumps over 2a and pushes it to index 3, past 2b. The result is [0, 1, 2b, 2a]: the equal items switched order. If you need stability, use insertion sort or merge sort.

Variations and follow-ups

Twists interviewers add

Knuth's gaps: 1, 4, 13, 40, 121, ...

Each gap is 3 × previous + 1. Start from the biggest gap below n / 3 and divide by 3 each round. The worst case drops to O(n^1.5), and the sequence is easy to compute.

Ciura's gaps: 1, 4, 10, 23, 57, 132, 301, 701

These were found by experiment and are among the fastest known in practice for lists up to a few thousand items. For longer lists, extend them by multiplying by about 2.25.

Gaps of the form `2^p × 3^q`

Using every number made only of the factors 2 and 3 (1, 2, 3, 4, 6, 8, 9, 12, ...) gives a proven worst case of O(n log² n). It needs many passes, so it is slower in practice than Ciura's gaps.

Comb sort

The same idea applied to bubble sort: compare and swap items gap apart, and shrink the gap by about 1.3 each pass until it reaches 1. It removes bubble sort's slow-moving small items at the end.

In an interview

Spot it, explain it, answer follow-ups

Shell sort rarely appears as an interview problem by name. It shows up as a follow-up: "insertion sort is slow when items are far from their place; how could you improve it?" The answer is to move items in big jumps first.
Explain it in one line: "insertion sort on items gap apart, with the gap shrinking to 1". Then say why it is always correct: the last pass is ordinary insertion sort.
Test by hand on 8 items with gaps 4, 2, 1. Write the gap-4 groups out as separate short lists to check that each one ends up sorted.
Expect "what is its time complexity?". The honest answer: it depends on the gap sequence. Halving gives O(n²) in the worst case, Knuth's gives O(n^1.5), and nobody knows a sequence that reaches O(n log n).

Where frontend code uses it

The same idea in real UI code

Small, self-contained code that needs a decent in-place sort without recursion, such as a tiny embedded script or a shader-like loop, sometimes uses Shell sort.
It shows why moving items far in one step helps, the same reason drag-and-drop UIs move a dragged card straight to its target slot instead of swapping it past each neighbor.
It is a useful bridge to understand why library sorts mix insertion sort with something faster for longer lists.

Shell sort

The idea

An everyday example

Tidying a bookshelf from across the room first

From the slow way to shell sort

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

Go further

Why it works

Going deeper

Why it ends sorted

Gap sequences and speed

Not stable

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Knuth's gaps: 1, 4, 13, 40, 121, ...

Ciura's gaps: 1, 4, 10, 23, 57, 132, 301, 701

Gaps of the form `2^p × 3^q`

Comb sort

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Tidying a bookshelf from across the room first

From the slow way to shell sort

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

Go further

Why it works

Going deeper

Why it ends sorted

Gap sequences and speed

Not stable

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Knuth's gaps: 1, 4, 13, 40, 121, ...

Ciura's gaps: 1, 4, 10, 23, 57, 132, 301, 701

Gaps of the form 2^p × 3^q

Comb sort

In an interview

Where frontend code uses it

Related algorithms

Gaps of the form `2^p × 3^q`