Insertion sort is fast when an element is
already close to its final spot, and slow when it isn't — a small value stuck at the far end
of the array has to shift past every element in between, one slot at a time. Shell sort's
fix: before doing plain insertion sort (elements one apart), first do the same shifting
comparison on elements far apart — a large gap — so a badly
out-of-place value can jump most of the distance to its final position in a single pass.
Shrink the gap each round, and finish with gap 1, which is exactly
insertion sort — but by then the array is already close to sorted, so that final pass is
cheap.
Enter a comma-separated list of numbers, then step through the sort. The accent bar is
the key being carried into place (the "hole"); the bordered bar is the
element gap slots behind it that the key is currently being compared against.
Watch the gap shrink in the log between passes, and notice the final gap-1
pass — ordinary insertion sort — do very little work, because the earlier passes already
did most of the sorting.
Think of a gap-g pass as running g completely independent
insertion sorts, interleaved: one over the elements at indices 0, g, 2g, ...,
another over 1, g+1, 2g+1, ..., and so on. Each of those sub-sequences ends the
pass fully sorted relative to itself — that's just insertion sort's own correctness argument,
applied g times to shorter sequences. An array that's "gap-g
sorted" for several different, shrinking values of g stays gap-sorted for the
larger values as smaller ones are applied — it doesn't get undone, only refined — until the
final gap-1 pass, which is a full ordinary insertion sort and produces a
correctly sorted array regardless of what came before. The earlier passes aren't required for
correctness; they're what makes that last pass fast, since few elements are still far from
home by the time it starts.
The gap sequence here is the simplest one — start at floor(n/2) and halve it
each round down to 1 — the sequence Shell himself used. See Pitfalls for what
that choice costs:
function shellSort(arr) {
const n = arr.length;
let gap = Math.floor(n / 2);
while (gap > 0) {
for (let i = gap; i < n; i++) {
const key = arr[i];
let hole = i;
while (hole >= gap && arr[hole - gap] > key) {
arr[hole] = arr[hole - gap]; // shift right by gap
hole -= gap;
}
arr[hole] = key;
}
gap = Math.floor(gap / 2);
}
return arr;
}Set gap = 1 permanently and this is byte-for-byte
insertion sort's own shift loop — shell sort is
that same loop, just run first at wider strides.
The gap sequence must actually reach 1 — stopping early leaves the array only
partially sorted, not fully. A tempting "optimization" is looping while
gap > 1 instead of gap > 0, on the theory that the last pass
barely does anything anyway. It doesn't barely do anything — for reverse-sorted input it does
most of the remaining work. Reverse-sorted [8, 7, 6, 5, 4, 3, 2, 1] with the loop
cut off at gap > 1 (so the final gap-1/plain-insertion-sort pass
never runs) produces [2, 1, 4, 3, 6, 5, 8, 7] — every adjacent pair still
reversed, because gap-2 only ever compared same-parity indices against each
other and no pass ever compared neighbors. Checked against the correct loop on every
reverse-sorted array from n=2 to n=19: the truncated version fails
on 13 of them, always leaving some adjacent-pair inversion the missing final pass would have
fixed.
It's not stable, even though gap-1 insertion sort alone is.
An earlier, wide-gap pass can move a value past an equal value that sits at a
different offset within the gap grouping, since the two are never directly compared until (if
ever) a later, smaller gap puts them in the same sub-sequence. Concretely, sorting the
tagged values [2#0, 2#1, 2#2, 0#3] (value#original-index, so three equal
2s followed by a 0) through the exact algorithm above produces
[0#3, 2#0, 2#2, 2#1] — the two equal 2s originally at positions 1
and 2 come out in the order 2, 1, swapped. Plain insertion sort's strict
> guarantees stability because it only ever compares adjacent
elements; shell sort loses that guarantee the moment a gap is wider than 1, since it compares
elements that aren't adjacent and can leapfrog an equal one sitting between them.
The gap sequence controls the worst case, and this page's sequence is a weak one.
Repeatedly halving n — Shell's own original choice — has a known
adversarial input class that drives it back to O(n²) comparisons, the same
worst case as plain insertion sort with none of the mitigation the wide passes are supposed
to buy. Better-studied sequences (Hibbard's 2^k - 1, Sedgewick's, or
Ciura's empirically-tuned constants) avoid that specific pathology and are provably or
empirically better, which is exactly why production sort implementations that use a
shell-sort-family algorithm don't use this simple halving sequence. No gap sequence has a
proven O(n log n) worst case — shell sort's real-world reputation as "good
enough, rarely the right choice when something else is available" comes from that open
question, not from a specific known flaw in the halving sequence alone.
Time: depends on the gap sequence — the only sorting algorithm on this
site where that's true. With the halving sequence shown above, worst case is
O(n²) (see Pitfalls); best case, on an already-sorted array, is O(n log n)
since every pass's inner while never fires and there are O(log n)
passes each doing an O(n) scan. Better sequences push the worst case down —
Hibbard's reaches O(n^1.5), and several sequences are conjectured (not proven)
to do better still. Space: O(1) extra, like
insertion sort — every pass sorts the array in
place, no second buffer at any gap width.
Compare with insertion sort, which shell sort
strictly generalizes (gap 1 only), and with
heap sort, which trades shell sort's
sequence-dependent, unproven worst case for a guaranteed O(n log n) at the same
O(1) space cost. See Choosing a Comparison Sort for how all ten
comparison sorts on this site stack up against each other.