Shell Sort

Sorting O(n log² n) O(1)

Insertion sort over shrinking gaps: distant elements move first, so the final pass has little work left.

Idle

Starting Shell Sort on 8 elements.

InvariantEvery chain 1 apart is sorted. Smaller gaps inherit that work, so the final pass has little left to do.

1/47

comparisons0moves0gap0i0j0key0

compareswapshiftselectsorted

shell-sort.c

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

How Shell Sort works

Run insertion sort over elements a gap apart, then shrink the gap. Distant elements jump close to their final spot early, so the final gap-1 pass finds an almost-sorted array.

Best case

Already sorted — every gap pass just verifies order: about O(n log n).

Worst case

Depends on the gap sequence; with n/2ᵏ gaps it degrades to O(n²).

When to use it

Simple in-place sort that beats plain insertion sort without recursion or extra memory.