Shell Sort

What is shell sort?

Shell sort is insertion sort with a head start. Insertion sort moves values one step at a time, so a small value near the end takes a long walk. Shell sort first sorts values that are far apart, so values can take big jumps toward where they belong. Then it shrinks the gap and repeats. The last round uses a gap of 1, which is plain insertion sort, but by then the list is nearly sorted, and that is exactly when insertion sort is fast.

It is named after Donald Shell, who published it in 1959. It has nothing to do with shells.

How it works, step by step

Press play above. Blue bars are being compared, orange bars are being swapped. Early compares are far apart. With each round they get closer, until they are neighbors.

1. Start with a gap g = n // 2.
2. For each position i from g to the end, run insertion sort with steps of g: while a[j - g] is bigger than a[j], swap them and move j back by g.
3. Halve the gap: g //= 2.
4. Repeat until the gap is 0. The last real round, with gap 1, finishes the job.

In the code, the inner while j >= g loop is insertion sort, with g where insertion sort has 1. The break fires as soon as a value is in place for this gap, which is what makes the later rounds quick.

Time and space complexity

Shell sort is unusual: its speed depends on the gaps you choose, and for many gap sequences nobody knows the exact average cost.

Best case, O(n log n): the list is already sorted. There are about log n gaps, and each round checks each value once and stops.

Worst case, O(n²) with the halving gaps shown here (Shell’s original). Some inputs keep values apart through every round until the last one, leaving the gap-1 insertion sort nearly all the work.

Average case: it depends. Better gap sequences avoid that problem. Knuth’s sequence (1, 4, 13, 40, …) has a worst case of O(n^1.5), and Ciura’s tested sequence (1, 4, 10, 23, 57, 132, …) is one of the fastest known in practice.

Space is O(1). It sorts in place.

Common mistakes

• Doing one pass per gap, like comb sort. Each gap needs a full insertion sort, where values keep moving back until they fit.
• Stepping j back by 1 instead of g, which breaks the gap sorting.
• Leaving the gap-1 round out. Only the last round guarantees the list is fully sorted.
• Expecting stability. Values jump over others across a gap, so shell sort is not stable.

When to use it

Shell sort is a good choice when you need a fast in-place sort with very little code and no recursion. It shows up in embedded systems and in some C standard libraries for that reason. It is also easy to tune: swap in a better gap sequence and it gets faster.

For everyday code, use your language’s built-in sort. It is faster on large lists and usually stable. And if you need a guaranteed O(n log n) in place, heap sort gives you that.

Questions

Is shell sort stable?

No. Moving values across a gap can jump one over an equal value.

What is the best gap sequence for shell sort?

There is no proven best. Ciura’s sequence (1, 4, 10, 23, 57, 132, 301, 701) is a popular choice because it tests fastest in practice.

How is shell sort related to insertion sort?

Each round is an insertion sort over values a gap apart. The last round, with gap 1, is plain insertion sort on a nearly sorted list.