Shell sort, explained

Insertion sort is slow when an item is far from its place, because it can only move one position at a time. Shell sort fixes that by first comparing items that are a gap apart, which moves them long distances quickly.

The gap is then made smaller, and the last pass uses a gap of 1, which is ordinary insertion sort on a list that is already nearly sorted.

How it works

• Choose a starting gap, for example half the list length.
• Do an insertion sort on items that are one gap apart.
• Make the gap smaller (for example, halve it).
• Repeat until the gap is 1 and the final pass finishes the job.

A small example

Sort this list:

12 34 54 2 3

After gap 2:  3 2 12 34 54
After gap 1:  2 3 12 34 54

After the first pass the list was already nearly sorted, so the last pass needed very little work.

What to know about its cost

• The speed depends on the gap sequence chosen.
• Worst case O(n²), but often much better in practice.
• Uses O(1) extra space and is not stable.

Where it works well

• Much faster than plain insertion sort on medium lists.
• No extra memory.

Where it struggles

• Speed depends on the gap sequence.
• Harder to analyse than other sorts, and not stable.

Try it yourself

Open the Sorting experiment, enter a list such as 12 34 54 2 3, choose Shell Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment