ShellSort.md

Shell Sort

← Back to index

Definition

Shell Sort generalizes insertion sort to allow exchanges of elements far apart by sorting elements at specific gap intervals and gradually reducing the gap until it becomes 1.

• Stable: No (generally)
• In-place: Yes
• Adaptive: Partially; performance depends on gap sequence

Pseudocode (Python)

def shell_sort(a, gaps=None):
    n = len(a)
    if gaps is None:
        # Ciura sequence extended
        gaps = [701, 301, 132, 57, 23, 10, 4, 1]
    for gap in gaps:
        for i in range(gap, n):
            temp = a[i]
            j = i
            while j >= gap and a[j - gap] > temp:
                a[j] = a[j - gap]
                j -= gap
            a[j] = temp
    return a

if __name__ == "__main__":
    print(shell_sort([12, 34, 54, 2, 3]))

Use cases

• In-place improvement over insertion sort for medium-sized arrays
• When data is too big for cache-friendly merge sort but needs better-than-quadratic behavior
• Systems where tuning gap sequence empirically yields robust performance

Recurrence relation

• Depends on gap sequence; for a sequence g1, g2, ..., gk with gk=1, cost ≈ Σ_i Θ(n · (n/gi)) for worst-case inversions within gap-separated subsequences
• Classic analysis gives between Θ(n^(3/2)) and Θ(n^2); with Ciura-like sequences, empirical ~Θ(n^{1.2}–n log n)

Python source: algorithms/comparison-based/code/shell_sort.py

C (C99)

#include <stdio.h>

void shell_sort(int a[], int n) {
    int gaps[] = {701,301,132,57,23,10,4,1};
    int gcount = sizeof(gaps)/sizeof(gaps[0]);
    for (int gi = 0; gi < gcount; ++gi) {
        int gap = gaps[gi];
        for (int i = gap; i < n; ++i) {
            int temp = a[i], j = i;
            while (j >= gap && a[j-gap] > temp) {
                a[j] = a[j-gap]; j -= gap;
            }
            a[j] = temp;
        }
    }
}

int main(void) {
    int a[] = {12,34,54,2,3};
    int n = sizeof(a)/sizeof(a[0]);
    shell_sort(a, n);
    for (int i = 0; i < n; ++i) printf("%d%s", a[i], i+1==n?"\n":" ");
}

C source: algorithms/comparison-based/code/shell_sort.c

C++ (C++17)

#include <bits/stdc++.h>
using namespace std;

void shell_sort(vector<int>& a) {
    vector<int> gaps = {701,301,132,57,23,10,4,1};
    int n = (int)a.size();
    for (int gap: gaps) {
        for (int i = gap; i < n; ++i) {
            int temp = a[i], j = i;
            while (j >= gap && a[j-gap] > temp) { a[j] = a[j-gap]; j -= gap; }
            a[j] = temp;
        }
    }
}

int main() {
    vector<int> a = {12,34,54,2,3};
    shell_sort(a);
    for (size_t i = 0; i < a.size(); ++i) cout << a[i] << (i+1==a.size()? '\n' : ' ');
}

C++ source: algorithms/comparison-based/code/shell_sort.cpp

Time and Space Complexity

• Depends on gap sequence; typical practical: ~O(n^(3/2)) worst with classic sequences, ~O(n log^2 n) with Sedgewick, near O(n log n) empirically with Ciura
• Worst: Between O(n^(3/2)) and O(n^2) depending on gaps
• Space: O(1)

Proof sketch of correctness

Each gap pass performs insertion sort on interleaved subsequences. As gaps reduce to 1, the array becomes nearly sorted, and the final insertion sort completes ordering. Correctness follows from insertion sort maintaining ordered subsequences and the final pass ensuring total order.

Example

Input: [12, 34, 54, 2, 3]

• gap=10→4→1 → final sorted: [2, 3, 12, 34, 54]

Variants

• Gap sequences: Shell’s original, Hibbard, Knuth, Sedgewick, Ciura

Practice problems (interview/competitive)

• Experiment with different gap sequences and measure comparisons/swaps
• Sort an array using Ciura’s sequence and compare to insertion sort
• Prove correctness for a chosen gap sequence via h-sorted property
• Implement shell sort that adapts to input size to choose gaps
• Show a counterexample where poor gap choices cause quadratic behavior