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.

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

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

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