Shell Sort Algorithm: C, C++, Java, Python & C# Code

Shell Sort is the algorithm that made insertion sort fast — and it did it in 1959 with one idea that still feels clever today: sort elements that are far apart first, so that by the time you compare neighbors, almost everything is already home. It remains genuinely useful (it ships inside bzip2 and embedded C libraries), and its open mathematical questions have kept computer scientists busy for six decades.

This guide explains how Shell Sort works with a step-by-step trace, why the gap sequence you choose changes its complexity class, and provides tested implementations in C (Knuth’s and Hibbard’s sequences), C++, Java, Python, and C#. Every program here was compiled and run — C with gcc -std=c11 -Wall -Wextra, C++ with g++ -std=c++17, Java on OpenJDK 21, Python 3, and C# on Mono — with the outputs shown captured from those runs.

Table of Contents

• What Is Shell Sort?
• How Shell Sort Works
• Gap Sequences: Why the Interval Choice Matters
• Shell Sort Complexity and Properties
• Shell Sort in C — Knuth's Sequence
• Shell Sort in C — Hibbard's Sequence
• Shell Sort in C++, Java, Python and C#
• Shell Sort vs Other Sorting Algorithms
• Where Shell Sort Is Used in Real Software
• Key Takeaways
• Frequently Asked Questions
• Conclusion

What Is Shell Sort?

Shell Sort is an in-place comparison sorting algorithm that generalizes insertion sort. Instead of comparing only adjacent elements, it insertion-sorts elements a fixed gap apart, then repeats with progressively smaller gaps until a final pass with gap 1. Because early passes move elements long distances cheaply, the final pass runs on a nearly sorted array — insertion sort’s best case.

The algorithm is named after Donald L. Shell, who published it in July 1959 in Communications of the ACM under the title “A High-Speed Sorting Procedure.” It was one of the first algorithms to break the O(n²) barrier that bubble and insertion sort live under — and, remarkably, its exact time complexity for the best possible gap sequence is still an open problem.

How Shell Sort Works

The recipe:

1. Pick a starting gap from a gap sequence (more on those below), based on the array size.
2. Gapped insertion sort: treat every set of elements that are gap positions apart as its own small subarray, and insertion-sort each one.
3. Shrink the gap to the next value in the sequence and repeat.
4. Finish with gap 1 — plain insertion sort, now running on an almost-sorted array where elements barely need to move.

Here is one real pass, traced on the array used by every implementation in this article — {6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5} with gap 4:

With gap 4, the array splits into four interleaved chains — positions {0,4,8} holding 6,7,2, positions {1,5,9} holding 4,1,8, positions {2,6,10} holding 9,0,5, and positions {3,7} holding 3,10. Each chain is insertion-sorted independently: 6,7,2 becomes 2,6,7, 4,1,8 becomes 1,4,8, and so on. One pass later the array reads 2 1 0 3 6 4 5 10 7 8 9 — nothing is fully sorted, yet everything is close to where it belongs. That is the whole trick: the closing gap-1 pass, which would cost O(n²) on a random array, now runs in nearly linear time. (These are the exact intermediate states printed by the C program below.)

Gap Sequences: Why the Interval Choice Matters

Shell Sort’s personality is entirely determined by its gap sequence — researchers have spent decades proposing better ones, and the choice changes the algorithm’s complexity class:

Three patterns worth noticing. Shell’s original halving sequence has a flaw: its gaps share factors, so the same elements keep meeting each other and worst-case inputs stay quadratic. Hibbard and Knuth fixed this with sequences whose gaps are relatively prime-ish, buying a provable n^1.5. And Ciura’s sequence — found by experiment, not formula — beats the theoretically-motivated ones in practice, a lovely reminder that this 66-year-old algorithm still isn’t fully understood. Knuth’s sequence remains the standard classroom-and-library default: simple to generate (gap = gap*3 + 1) and excellent for mid-sized arrays.

Shell Sort Complexity and Properties

The honest headline: unlike quicksort or merge sort, Shell Sort’s complexity is not one number — it is a function of the gap sequence, and for the best sequences nobody has proved what it is. The old single-value framing (“average O(n log n)”) oversimplifies to the point of being wrong.

Shell Sort in C — Knuth’s Sequence

Knuth’s gaps are generated on the fly: grow with gap*3 + 1 until you pass n/3, then shrink with (gap−1)/3 — no lookup table, no floating point:

#include <stdio.h>

void print(const int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d  ", a[i]);
    printf("\n");
}

/* Shell Sort with Knuth's gap sequence: 1, 4, 13, 40, 121, ... */
void shellsort(int a[], int n)
{
    /* start from the largest Knuth gap smaller than n/3 */
    int gap = 1;
    while (gap < n / 3)
        gap = gap * 3 + 1;          /* 1, 4, 13, 40, ... */

    for (; gap > 0; gap = (gap - 1) / 3) {
        /* gapped insertion sort */
        for (int i = gap; i < n; i++) {
            int tmp = a[i];
            int j;
            for (j = i; j >= gap && a[j - gap] > tmp; j -= gap)
                a[j] = a[j - gap];  /* shift larger elements right */
            a[j] = tmp;
        }
        printf(" Gap %d: ", gap);
        print(a, n);
    }
}

int main(void)
{
    int array[] = { 6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5 };
    int size = sizeof(array) / sizeof(array[0]);

    shellsort(array, size);
    printf("Sorted array: ");
    print(array, size);
    return 0;
}

Output:

 Gap 4: 2  1  0  3  6  4  5  10  7  8  9  
 Gap 1: 0  1  2  3  4  5  6  7  8  9  10  
Sorted array: 0  1  2  3  4  5  6  7  8  9  10

For 11 elements, Knuth’s sequence uses just two passes — gap 4 (the pass traced in the diagram above), then gap 1 on the almost-sorted result.

Shell Sort in C — Hibbard’s Sequence

Hibbard’s gaps are 2ᵏ − 1 (1, 3, 7, 15, …). A neat property makes the code simple: integer-halving a Hibbard gap gives the previous Hibbard gap (7 → 3 → 1), so after finding the largest starting gap — with pure integer arithmetic, no pow()/log() needed — plain gap /= 2 walks the sequence:

#include <stdio.h>

void print(const int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d  ", a[i]);
    printf("\n");
}

/* Shell Sort with Hibbard's gap sequence: 1, 3, 7, 15, 31, ... (2^k - 1) */
void shellsort(int a[], int n)
{
    /* largest 2^k - 1 that is smaller than n -- no floating point needed */
    int gap = 1;
    while (gap * 2 + 1 < n)
        gap = gap * 2 + 1;          /* 1, 3, 7, 15, ... */

    for (; gap > 0; gap /= 2) {     /* 7 -> 3 -> 1: halving stays in sequence */
        for (int i = gap; i < n; i++) {
            int tmp = a[i];
            int j;
            for (j = i; j >= gap && a[j - gap] > tmp; j -= gap)
                a[j] = a[j - gap];
            a[j] = tmp;
        }
        printf(" Gap %d: ", gap);
        print(a, n);
    }
}

int main(void)
{
    int array[] = { 6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5 };
    int size = sizeof(array) / sizeof(array[0]);

    shellsort(array, size);
    printf("Sorted array: ");
    print(array, size);
    return 0;
}

Output:

 Gap 7: 6  2  8  3  7  1  0  10  4  9  5  
 Gap 3: 0  2  1  3  5  4  6  7  8  9  10  
 Gap 1: 0  1  2  3  4  5  6  7  8  9  10  
Sorted array: 0  1  2  3  4  5  6  7  8  9  10

Same array, different rhythm: three passes (7, 3, 1) instead of two. Which sequence wins depends on the data and size — which is precisely why the sequence table above exists.

Shell Sort in C++, Java, Python and C#

The algorithm translates almost line-for-line — the differences are each language’s container idioms, not the logic. All four use Knuth’s gaps and the same array, and each was compiled (or interpreted) and run with the identical result: Sorted array: 0 1 2 3 4 5 6 7 8 9 10.

C++ (g++ -std=c++17 -Wall -Wextra):

#include <iostream>
#include <vector>

// Shell Sort with Knuth's gaps -- modern C++
void shellSort(std::vector<int>& a)
{
    int n = static_cast<int>(a.size());
    int gap = 1;
    while (gap < n / 3)
        gap = gap * 3 + 1;

    for (; gap > 0; gap = (gap - 1) / 3) {
        for (int i = gap; i < n; i++) {
            int tmp = a[i];
            int j = i;
            for (; j >= gap && a[j - gap] > tmp; j -= gap)
                a[j] = a[j - gap];
            a[j] = tmp;
        }
    }
}

int main()
{
    std::vector<int> data { 6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5 };
    shellSort(data);

    std::cout << "Sorted array: ";
    for (int v : data)
        std::cout << v << "  ";
    std::cout << '\n';
    return 0;
}

Java (OpenJDK 21):

public class ShellSort {

    // Shell Sort with Knuth's gaps
    static void shellSort(int[] a) {
        int n = a.length;
        int gap = 1;
        while (gap < n / 3)
            gap = gap * 3 + 1;

        for (; gap > 0; gap = (gap - 1) / 3) {
            for (int i = gap; i < n; i++) {
                int tmp = a[i];
                int j = i;
                for (; j >= gap && a[j - gap] > tmp; j -= gap)
                    a[j] = a[j - gap];
                a[j] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = { 6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5 };
        shellSort(data);

        StringBuilder sb = new StringBuilder("Sorted array: ");
        for (int v : data)
            sb.append(v).append("  ");
        System.out.println(sb);
    }
}

Python 3:

def shell_sort(a):
    """Shell Sort with Knuth's gap sequence: 1, 4, 13, 40, ..."""
    n = len(a)
    gap = 1
    while gap < n // 3:
        gap = gap * 3 + 1

    while gap > 0:
        for i in range(gap, n):           # gapped insertion sort
            tmp = a[i]
            j = i
            while j >= gap and a[j - gap] > tmp:
                a[j] = a[j - gap]
                j -= gap
            a[j] = tmp
        gap = (gap - 1) // 3

data = [6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5]
shell_sort(data)
print("Sorted array:", "  ".join(map(str, data)))

C# (compiled with Mono, runs identically on .NET):

using System;

class ShellSortDemo
{
    // Shell Sort with Knuth's gaps
    static void ShellSort(int[] a)
    {
        int n = a.Length;
        int gap = 1;
        while (gap < n / 3)
            gap = gap * 3 + 1;

        for (; gap > 0; gap = (gap - 1) / 3)
        {
            for (int i = gap; i < n; i++)
            {
                int tmp = a[i];
                int j = i;
                for (; j >= gap && a[j - gap] > tmp; j -= gap)
                    a[j] = a[j - gap];
                a[j] = tmp;
            }
        }
    }

    static void Main()
    {
        int[] data = { 6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5 };
        ShellSort(data);
        Console.WriteLine("Sorted array: " + string.Join("  ", data));
    }
}

Shell Sort vs Other Sorting Algorithms

Where Shell Sort earns its keep against each neighbor: it upgrades insertion sort (its direct ancestor) from quadratic to sub-quadratic while keeping the same tiny code and O(1) memory; against quicksort it trades some speed for no recursion and no pathological O(n²) input (with Hibbard/Knuth gaps, the n^1.5 bound is a guarantee); and against merge sort it trades stability and guaranteed n log n for zero extra memory. That combination — small code, no stack, no allocation, decent guaranteed bound — is a niche, but a real one.

Where Shell Sort Is Used in Real Software

Two verifiable, load-bearing deployments — both driven by exactly the trade-offs above:

• bzip2. The compressor’s block-sorting code (blocksort.c) contains a Shell Sort with the increments 1, 4, 13, 40, 121, … — Knuth’s sequence — used to sort small buckets inside its main sorting machinery. Open the source and the increment table is right there.
• uClibc / embedded C libraries. The lightweight C library used across embedded Linux implements its qsort() as a Shell Sort — chosen precisely because it needs no recursion, no extra memory, and has no killer worst-case input, all scarce commodities on small devices.

The general rule they illustrate: Shell Sort appears where memory is tight, recursion is unwelcome, and arrays are modest — firmware, kernels’ corners, and library internals — rather than in application code, where the standard library’s sort (typically introsort or Timsort) is the right call.

Key Takeaways

• Shell Sort = insertion sort with a shrinking gap: far-apart elements are sorted first, so the final gap-1 pass runs on a nearly sorted array.
• The gap sequence determines the complexity class — from O(n²) for Shell’s original halving gaps to Θ(n^1.5) for Hibbard/Knuth, O(n log²n) for Pratt, and empirically best (but unproven) for Ciura’s 1, 4, 10, 23, 57, ….
• Knuth’s gaps are the practical default: generated by gap = gap*3 + 1, no tables, no floating point.
• Shell Sort is in-place (O(1) space), iterative (no recursion), adaptive — and not stable.
• It ships in real software — bzip2’s block sorter and uClibc’s qsort — wherever memory and stack are scarce.
• The algorithm’s exact average-case complexity for optimal gaps is still an open problem, 66 years after Donald Shell’s 1959 paper.

Frequently Asked Questions

Conclusion

Shell Sort occupies a rare spot in the algorithms canon: simple enough to write from memory, subtle enough that its exact complexity is still unsolved, and practical enough to be shipping inside your compression tools right now. Studying it teaches something the O(n log n) heavyweights don’t — that an algorithm’s behavior can hinge entirely on one tuning decision, and that a sequence found by experiment can beat every formula on the books.

If this walkthrough clicked, the natural companions are its ancestor and its rivals — insertion sort, quicksort, and merge sort — and the rest of our algorithms section builds from here toward graphs, trees, and the classics like Kruskal’s algorithm that put sorting to work inside bigger problems.

See also: Quick Sort, Bubble Sort, Insertion Sort, Selection Sort