Shell Sort with Sedgewick Gaps

Shell sort with Sedgewick gaps uses a carefully designed sequence that improves both theoretical and practical performance over earlier sequences such as Shell and Hibbard.

Two common Sedgewick sequences are used in practice. A widely cited version is:

$$ g_k = \begin{cases} 9 \cdot 2^k - 9 \cdot 2^{k/2} + 1 & \text{if } k \text{ even}
8 \cdot 2^k - 6 \cdot 2^{(k+1)/2} + 1 & \text{if } k \text{ odd} \end{cases} $$

This produces gaps such as:

$$ 1, 5, 19, 41, 109, \dots $$

You use all values less than $n$, in decreasing order.

Problem

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

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

Gap Sequence

Generate all Sedgewick gaps less than $n$, then apply them in descending order.

Example for $n = 50$:

$$ 41, 19, 5, 1 $$

Algorithm

For each gap, perform insertion sort on elements spaced by that gap.

shell_sort_sedgewick(A):
    n = length(A)

    gaps = generate_sedgewick_gaps(n)

    for gap in reverse(gaps):
        for i from gap to n - 1:
            key = A[i]
            j = i

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

            A[j] = key

Example

Let

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

For $n = 8$, Sedgewick gaps are:

$$ 5, 1 $$

Gap 5:

→ reduces long-distance inversions

Gap 1:

→ final insertion sort

Result:

$$ [1, 3, 4, 5, 6, 7, 8, 9] $$

Correctness

Each gap enforces ordering among elements spaced by that gap. As gaps decrease, the array becomes increasingly structured. The final pass with gap 1 ensures full sorting.

Complexity

case	time
worst	about $O(n^{4/3})$
average	close to $O(n^{4/3})$
best	$O(n \log n)$

Space complexity:

$$ O(1) $$

Properties

• in-place
• not stable
• strong practical performance
• widely used in tuned Shell sort implementations

When to Use

Sedgewick gaps are preferred when using Shell sort in practice. They offer a good balance between simplicity and performance without requiring complex tuning.

Implementation

def sedgewick_gaps(n):
    gaps = []
    k = 0
    while True:
        if k % 2 == 0:
            gap = 9 * (2**k) - 9 * (2**(k//2)) + 1
        else:
            gap = 8 * (2**k) - 6 * (2**((k+1)//2)) + 1
        if gap >= n:
            break
        gaps.append(gap)
        k += 1
    return gaps

def shell_sort_sedgewick(a):
    n = len(a)
    gaps = sedgewick_gaps(n)

    for gap in reversed(gaps):
        for i in range(gap, n):
            key = a[i]
            j = i

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

            a[j] = key

    return a

func SedgewickGaps(n int) []int {
    gaps := []int{}
    for k := 0; ; k++ {
        var gap int
        if k%2 == 0 {
            gap = 9*(1<<k) - 9*(1<<(k/2)) + 1
        } else {
            gap = 8*(1<<k) - 6*(1<<((k+1)/2)) + 1
        }
        if gap >= n {
            break
        }
        gaps = append(gaps, gap)
    }
    return gaps
}

func ShellSortSedgewick[T constraints.Ordered](a []T) {
    gaps := SedgewickGaps(len(a))

    for g := len(gaps) - 1; g >= 0; g-- {
        gap := gaps[g]
        for i := gap; i < len(a); i++ {
            key := a[i]
            j := i

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

            a[j] = key
        }
    }
}