Shell Sort Visualization

Shell Sort runs insertion sort on elements far apart first, then on closer and closer elements.

How it works

Shell Sort is Insertion Sort with a head start. Instead of comparing neighbours, it first sorts elements that are a large gap apart, so values far from home can jump most of the way in one move. It then halves the gap and repeats, and the final pass with a gap of one is ordinary Insertion Sort on data that is already almost sorted.

How fast it is depends on the gap sequence. This version halves the gap each round (Shell's original sequence), which is roughly n^1.5 on random data; better sequences get closer to n log n. It sorts in place, needs very little code, and is a common choice for small embedded systems.

What to watch for

Watch coarse colour bands form across the whole picture, then sharpen with each pass until the final pass smooths out the last small errors.

Complexity

Best

n log n

Average

n^1.5

Worst

n²

Extra space

1

Stable

No

Race it

Same shuffle, same speed, one winner: Shell vs Insertion. Or open the studio to try other layouts, sizes and speeds, and make a video of it.

FAQ