Shell Sort

Diminishing-Gap Insertion

1:00

Shell sort generalizes insertion sort with a shrinking gap sequence — sorting far-apart elements first so the final gap-1 pass is cheap — and its complexity is determined entirely by the gap sequence chosen.

By the end, you can

Explain why plain insertion sort is slow for far-from-home elements and how Shell sort fixes it.
Trace the gap-4, gap-2, and gap-1 passes of Shell sort on a small array.
Identify which indices belong to a given gap-group and the values they contain.
State the initial gap for a given array length and the number of passes the halving sequence makes.
Describe the key invariant: why earlier gap-pass orderings are preserved by later passes.
Match Shell's halving, Knuth's, and Pratt's gap sequences to their complexity bounds.
Compute the next term in Knuth's sequence using the recurrence g = 3·g + 1.
Classify Shell sort as in-place, adaptive, comparison-based, and not stable.

Up next in Searching & Sorting