Shell Sort with Shell Gaps

Shell sort with Shell gaps uses the original gap sequence proposed for Shell sort. The sequence starts with roughly half the array length and repeatedly halves the gap until it reaches 1.

This version is simple and easy to implement, but its worst-case behavior remains quadratic.

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

For an array of length $n$ , the Shell gap sequence is:

\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{n}{4} \right\rfloor, \left\lfloor \frac{n}{8} \right\rfloor, \dots, 1

For example, if $n = 16$ , the gaps are:

8, 4, 2, 1

Algorithm

For each gap, perform insertion sort over subsequences whose elements are separated by that gap.

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

    while gap > 0:
        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

        gap = gap // 2

Example

Let

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

For $n = 8$ , the gaps are:

4, 2, 1

Gap 4 pass:

compare and insert among index groups $(0,4)$ , $(1,5)$ , $(2,6)$ , $(3,7)$

After this pass:

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

Gap 2 pass partially orders even and odd index groups:

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

Gap 1 pass finishes with insertion sort:

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

Correctness

Each gap pass sorts every subsequence formed by taking elements at distance $g$ . After the final gap $g = 1$ , the whole array is one subsequence, so the final pass is ordinary insertion sort over the entire array. Therefore the output is sorted.

Complexity

case	time
best	$O(n \log n)$
worst	$O(n^2)$
average	depends on input

Space complexity:

O(1)

Properties

in-place
not stable
simple gap sequence
weaker than many later Shell sort gap sequences

When to Use

Use Shell gaps when implementation simplicity matters more than precise performance. For production sorting, prefer better gap sequences such as Hibbard, Sedgewick, Tokuda, or Ciura.

Implementation

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

    while gap > 0:
        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

        gap //= 2

    return a

func ShellSortShellGaps[T constraints.Ordered](a []T) {
    n := len(a)

    for gap := n / 2; gap > 0; gap /= 2 {
        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
        }
    }
}