Insertion sort is slow because elements crawl one step at a time. Shellsort lets them jump a gap first — sort everything a gap apart, then shrink the gap to 1 — so a small element far from home leaps most of the way early. Simple, in-place, and it runs on the array. And the best gap sequence is still an open problem.
THE TECHNIQUE h-sort with a shrinking gap
Pick a decreasing sequence of gaps ending in 1. For each gap h, run an insertion sort on the sub-sequences that are h apart (an h-sort). Large gaps move elements far cheaply; by the time the gap is 1, the array is nearly sorted, so the final insertion pass is fast. Below, gaps [5, 3, 1]. live demo
HISTORY & CREDIT the inventor gave it the wrong gaps
“Shellsort” sounds like seashells or a Unix shell — it is just a metaphor Donald Shell’s surname. And its own default gaps are bad. cited
1959 · Donald L. Shell (General Electric) publishes the diminishing-increment sort in CACM. His gap sequence is N/2, N/4, …, 1. the catch · those gaps are Θ(N²) worst case — when N is a power of two, even and odd positions never meet until the last pass. The inventor supplied the idea, not a good schedule. the fixes · Hibbard (2k−1 → N1.5), Pratt, Sedgewick, and Ciura’s empirical 1, 4, 10, 23, 57, 132, 301, 701 are all far better. still open · the exact worst-case complexity of the best gap sequence is an unsolved problem — rare for so simple an algorithm.
A 60-year-old sort whose optimal tuning nobody has proven. gaps: open problem
RECOMMEND FOR I-13 insertion sort with a stride
Shellsort is insertion sort with a gap — indexed reads and writes on one bounded array, with the gap as the stride. No extra buffer, no bignum, no bitwise:
def hsort(I a, I i, I gap, I n) { // one gapped insertion pass
if i >= n { -> a }
// shift a[i] left in steps of `gap` while out of order ...
-> hsort(a, i + 1, gap, n)
}
Recommend:nothing new — a strict no-wall: it is binary-search-free insertion sort (dart 042’s cousin) done at a stride, in place on the array. The gap sequence is a small bounded array of integers. Note: unlike merge sort (070) it needs no O(n) buffer — fully in place — and unlike quicksort (045) it has no bad-pivot cliff; the only mystery is mathematical (the optimal gaps), not one I-13 can or need resolve.