Shell Sort

Shell sort extends insertion sort by allowing exchanges of elements that are far apart. It sorts elements at a certain gap, then progressively reduces the gap until it becomes 1. The final pass with gap 1 is a standard insertion sort, but on a partially ordered array.

This reduces the number of shifts required compared to plain insertion sort.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Algorithm

Choose a sequence of gaps. For each gap $g$ , perform insertion sort on elements spaced by $g$ .

shell_sort(A):
    n = length(A)
    gap = n // 2

    while gap > 0:
        for i from gap to n - 1:
            temp = A[i]
            j = i

            while j >= gap and A[j - gap] > temp:
                A[j] = A[j - gap]
                j = j - gap

            A[j] = temp

        gap = gap // 2

Example

Let

A = [8, 5, 3, 7, 6, 2, 4, 1]

Gap = 4:

→ partially sorted groups

Gap = 2:

→ more refined ordering

Gap = 1:

→ final insertion sort

Final result:

[1,2,3,4,5,6,7,8]

Correctness

Each pass ensures that elements separated by the current gap are sorted. As the gap decreases, elements move closer to their correct positions. When the gap becomes 1, the array is sufficiently structured so that insertion sort completes efficiently.

Complexity

Depends on gap sequence:

gap sequence	worst time
simple halving	$O(n^2)$
Hibbard	$O(n^{3/2})$
Sedgewick	$O(n^{4/3})$ (empirical)

Space complexity:

O(1)

Properties

in-place
not stable
reduces large inversions early

When to Use

Shell sort performs well for medium-sized arrays where simplicity and low memory usage are important. It is faster than quadratic sorts in practice but slower than optimal $O(n \log n)$ algorithms.

Implementation

def shell_sort(a):
    n = len(a)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = a[i]
            j = i

            while j >= gap and a[j - gap] > temp:
                a[j] = a[j - gap]
                j -= gap

            a[j] = temp

        gap //= 2

    return a

func ShellSort[T constraints.Ordered](a []T) {
    n := len(a)
    for gap := n / 2; gap > 0; gap /= 2 {
        for i := gap; i < n; i++ {
            temp := a[i]
            j := i

            for j >= gap && a[j-gap] > temp {
                a[j] = a[j-gap]
                j -= gap
            }

            a[j] = temp
        }
    }
}