Shell Sort

By Victor Arce

Shell sort is insertion sort with a head start. Plain insertion sort only ever moves a value one step at a time, so a small value stuck at the far right takes many moves to reach the front. Shell sort fixes that by first comparing and swapping elements a large gap apart, then shrinking the gap, so values can leap most of the way home early — and by the time the gap is 1, the array is nearly sorted and the final insertion-sort pass is cheap.

Step through it below. Each pass works at a gap (8, 4, 2, … 1); the two highlighted cells are the pair being compared across the gap, and a swap makes a value jump several places at once. Toggle show log to follow along.

How it works

Pick a decreasing gap sequence — here n/2, n/4, …, 1. For each gap, run an insertion sort that compares each element with the one gap positions to its left, swapping while it is smaller and stepping back by gap each time. Large gaps move values long distances in few swaps and scatter them roughly into place; small gaps fine-tune. The last pass always uses gap 1 — an ordinary insertion sort, but now over an almost-sorted array, which is its best case.

Cost

Shell sort is in-placeIn-place: sorts within the original array using only a little extra memory (no second array). and its speed depends entirely on the gap sequence. The simple halving sequence used here is O(n²)O(n²) — quadratic time: the work grows with the square of the number of items. in the worst case, but good sequences (Hibbard, Sedgewick, …) bring it down to about O(n^1.3)–O(n log²n) — far better than plain insertion sort and often competitive for medium inputs. It is not stableStable: equal values keep their original relative order after sorting. (gapped swaps reorder equal values), but needs no extra memory, which makes it popular in constrained settings.

Back to Sorting Algorithms