Shell Sort is insertion sort, generalised. Standard insertion sort only moves elements one step at a time — an element at position 7 that belongs at position 0 needs 7 swaps. Shell Sort fixes this by first sorting elements that are far apart, so by the time gap=1 runs, every element is close to where it needs to be.
The key insight: insertion sort is nearly O(n) on nearly-sorted input. Shell Sort manufactures that nearly-sorted condition through the gap passes.
Shell Sort runs multiple passes with decreasing gap sizes. Each pass does insertion sort on elements that are 'gap' positions apart. The final pass (gap=1) is standard insertion sort.
A single swap with gap=8 moves an element 8 positions. Standard insertion sort would need 8 adjacent swaps for the same result. This pre-sorting makes the final pass nearly O(n).
The gap sequence determines the time complexity. Knuth's sequence (1, 4, 13, 40…) gives roughly O(n^1.5). Hibbard's sequence gives O(n^1.5). The best known gives O(n log² n).
Shell Sort is in-place — O(1) extra space. No additional arrays or recursive call stack beyond O(log n) for the gap sequence.
TIPWatch the gap=1 pass closely. Notice how few swaps it needs compared to the first pass. That's the whole idea — the large-gap passes do the heavy lifting cheaply so the final pass is almost free.