# Shell Sort with Hibbard Gaps

# Shell Sort with Hibbard Gaps

Shell sort with Hibbard gaps replaces the simple halving sequence with a more structured progression:

$$
g_k = 2^k - 1
$$

This sequence produces gaps such as:

$$
1, 3, 7, 15, 31, \dots
$$

In practice, you use the largest value less than $n$, then proceed in decreasing order down to 1.

This improves performance over the basic Shell gap sequence by reducing long-distance disorder more effectively.

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

Construct all values of the form:

$$
2^k - 1 < n
$$

Sort them in descending order and use them as gaps.

Example for $n = 20$:

$$
15, 7, 3, 1
$$

## Algorithm

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

```id="k2v9x3"
shell_sort_hibbard(A):
    n = length(A)

    gaps = []
    k = 1
    while (2^k - 1) < n:
        gaps.append(2^k - 1)
        k = k + 1

    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$, Hibbard gaps are:

$$
7, 3, 1
$$

Gap 7:

→ compare elements far apart

Gap 3:

→ reduce disorder further

Gap 1:

→ final insertion sort

Result:

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

## Correctness

Each gap sorts subsequences formed by stepping through the array with stride $g$. As gaps decrease, elements move closer to their correct positions. The final gap of 1 ensures a fully sorted sequence.

## Complexity

| case    | time               |
| ------- | ------------------ |
| worst   | $O(n^{3/2})$       |
| average | about $O(n^{3/2})$ |
| best    | $O(n \log n)$      |

Space complexity:

$$
O(1)
$$

## Properties

* in-place
* not stable
* better theoretical bounds than simple gaps

## When to Use

Hibbard gaps provide a good balance between simplicity and performance. They are suitable when you want a predictable improvement over naive Shell sort without complex tuning.

## Implementation

```id="m7x2p4"
def shell_sort_hibbard(a):
    n = len(a)

    gaps = []
    k = 1
    while (2**k - 1) < n:
        gaps.append(2**k - 1)
        k += 1

    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="q5k9z1"
func ShellSortHibbard[T constraints.Ordered](a []T) {
    n := len(a)

    var gaps []int
    for k := 1; (1<<k)-1 < n; k++ {
        gaps = append(gaps, (1<<k)-1)
    }

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

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

            a[j] = key
        }
    }
}
```