# Shell Sort with Sedgewick Gaps

# 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.

```id="k8x3p2"
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

```id="m4p9x1"
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
```

```id="z7k2q5"
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
        }
    }
}
```