Shell sort

Shell sort is an extension of insertion sort that compares elements far apart, gradually reducing the gap until it’s 1 (at which point it becomes a regular insertion sort, but on data that’s now nearly sorted). Named for Donald Shell (1959).

The intuition: insertion sort is fast on nearly-sorted data ($O(n)$) but slow on randomized data ($O(n^2)$). Shell sort uses big strides to get the data nearly sorted cheaply, then a final pass of insertion sort finishes the job.

Algorithm

1. Choose a gap sequence (e.g., $g=N/2,N/4,\dots ,1$).
2. For each gap $g$:
   • Treat the array as $g$ interleaved subarrays (every $g$-th element forms a subarray).
   • Sort each subarray using insertion sort.
3. Repeat with smaller and smaller gaps until $g=1$.

The last pass with $g=1$ is plain insertion sort — but by this point, the array is “almost sorted” because the previous passes moved elements close to their final positions over long distances.

Gap sequence

The choice of gap sequence affects performance significantly:

• Shell’s original: $g_k=N/2^k$, i.e., $N/2,N/4,N/8,\dots ,1$. Worst case $O(n^2)$.
• Sedgewick’s sequence: more complex formula, worst case $O(n^{4/3})$.
• Pratt’s sequence: $O(n{\log }^{2}n)$ but more comparisons per pass.

The PDF uses $g=N/3+1$, then $g^{\prime }=g/3+1$, etc. — a variant of the standard halving approach.

Worked example

For an array of size 12 with initial gap 4:

Sort 4 interleaved subarrays of size 3 each. Then reduce gap to 2 — sort 2 interleaved subarrays of size 6. Finally gap = 1 — one pass of insertion sort over the now-mostly-sorted array.

Big O

• Best case: $O(n\log n)$.
• Worst case: depends on gap sequence, ranges from $O(n^{4/3})$ to $O(n^2)$.

Shell sort’s average case is hard to analyze precisely — it depends on the gap sequence and on input properties. In practice, it’s faster than $O(n^2)$ but slower than $O(n\log n)$ sorts on random data.

Why it works

Insertion sort moves an element to its correct position by shifting other elements one slot at a time. If a small element is at the end of the array and needs to go to the start, it takes $n$ shifts.

Shell sort’s gap-based comparisons can move that element multiple positions per swap (across the gap), so the total movement work is dramatically reduced. By the time gap = 1, every element is close to its final position, and insertion sort’s $O(n)$ best case kicks in.

When to use it

Shell sort is rarely used in production today — quicksort, merge sort, and timsort all dominate. But it’s worth knowing because:

• Simple to implement (small constant factor).
• In-place, $O(1)$ extra memory.
• Decent performance on small to medium arrays.

Its main historical relevance is as the first sorting algorithm to break the $O(n^2)$ barrier in practical use.

For the more efficient $O(n\log n)$ sorts that displaced Shell sort, see Quick sort, Merge sort, Heap sort. For the simple $O(n^2)$ baseline, see Selection sort and Bubble sort.