Why does insertion sort get slow?

Insertion sort is genuinely fast on a "nearly sorted array." But it has one weakness: when a small value sits at the very back, it has to be shifted to its place (the front) one slot at a time. Nine slots away means nine shifts; a hundred away means a hundred. The farther the value, the worse it hurts.

Example: in [8, 5, 3, 9, 2, 7, 4, 1, 6], the 1 is near the end (index 7). With insertion sort, 1 must push past its neighbors seven times to reach the front.

Because of this "move one slot at a time" behavior, insertion sort slows down to O(n²) on random arrays.

The core idea — look across a "gap"

Shell sort's insight is simple: don't compare neighbors from the start — order far-apart elements first.

•First, insertion-sort only the elements that are a gap apart. (e.g. with gap=4: indices 0·4·8 together, 1·5 together, …)
•Then halve the gap to look more finely. (4 → 2 → 1)
•The final gap = 1 pass is really just plain insertion sort. But by then the array is already nearly sorted, so there is almost nothing to move.

A common gap sequence starts at half of the array size n and halves each round: n/2 → n/4 → … → 1.

Why does a gap make it faster?

The trick is the "big jump."

When the gap is large, a small value stuck far in the back jumps a long distance in a single swap. In the example above, 1 leaps far toward the front in one of the large-gap passes — completely unlike insertion sort's one-slot crawl.

So by the time the gap shrinks to gap = 1, the amount left to move has dropped sharply. The large gaps arrange the "big picture" first, and the small gap only does the "finishing touches."

In short, the flow is:

1. Start with gap = n/2

2. Insertion-sort each group of elements that are a gap apart

3. Halve the gap and repeat step 2

4. Done once the gap = 1 pass finishes

See it with your own eyes

As the gap shrinks 4 → 2 → 1, far-apart bars get compared (yellow) and swapped (red), and small values land near the front via big jumps. We built the entire process as a step-by-step visualization — with the gap value and variable changes visible at each step.

👉 Shell Sort — watch the step-by-step visualization

"Order from far away across a gap" sounds abstract in text, but once you watch the bars move in big jumps, "ah, that's why it's faster" lands instantly.