Shell Sort in C – Integer Array with Gap Sequence Explained

Shell sort is a generalization of insertion sort that sorts elements far apart before sorting adjacent ones. Invented by Donald Shell in 1959, it repeatedly applies insertion sort on sublists of decreasing “gap” sizes until the gap reaches 1 — at which point one final insertion sort on the nearly-sorted array runs in near-linear time.

The original post used gets() (a dangerous function removed in C11) to sort a character string with a fixed set of gaps {9,5,3,2,1}. This rewrite applies Shell sort to an integer array using the standard n/2 halving gap sequence, compiles with zero warnings under gcc -ansi -Wall -Wextra, and demonstrates the algorithm on three test cases.

How Shell Sort Works

Start with gap = n/2 (half the array size).
Do an insertion sort on every sublist of elements spaced “gap” apart.
Halve the gap: gap = gap/2.
Repeat until gap = 1. The final pass is a standard insertion sort on a nearly-sorted array.

Example with gap = 4, then 2, then 1 on array [64, 25, 12, 22, 11]:

gap=2: compare positions 0&2, 1&3, 2&4 → [12, 22, 64, 25, 11] ... partially ordered
gap=1: final insertion sort on nearly-sorted → [11, 12, 22, 25, 64]

C Program for Shell Sort

/* Shell sort in C — integer array sort using Shell's gap sequence
 * Compile: gcc -ansi -Wall -Wextra shellsort.c -o shellsort */
#include <stdio.h>

void shell_sort(int arr[], int n)
{
    int gap, i, j, temp;

    /* gap = n/2, n/4, n/8, ... 1 (Shell's original sequence) */
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

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

int main(void)
{
    int a[] = {64, 25, 12, 22, 11};
    int b[] = {5, 1, 4, 2, 8, 3, 7, 6};
    int c[] = {100};
    int na = 5, nb = 8, nc = 1;

    printf("Test 1: "); print_array(a, na);
    shell_sort(a, na);
    printf("Sorted: "); print_array(a, na);

    printf("\nTest 2: "); print_array(b, nb);
    shell_sort(b, nb);
    printf("Sorted: "); print_array(b, nb);

    printf("\nTest 3 (single): "); print_array(c, nc);
    shell_sort(c, nc);
    printf("Sorted: "); print_array(c, nc);

    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra shellsort.c -o shellsort
./shellsort

Sample Output

Test 1: 64 25 12 22 11
Sorted: 11 12 22 25 64

Test 2: 5 1 4 2 8 3 7 6
Sorted: 1 2 3 4 5 6 7 8

Test 3 (single): 100
Sorted: 100

Gap-by-Gap Trace: Sorting [64, 25, 12, 22, 11] (n=5)

Pass	Gap	State after pass	What happened
1	2	[12, 22, 64, 25, 11]	Compare/sort pairs at distance 2: (64,12)→swap, (25,22)→no swap, (12,11)→insert 11 before 64
2	1	[11, 12, 22, 25, 64]	Standard insertion sort on nearly-sorted array — very few moves needed

Code Explanation

Outer loop (gap) — starts at n/2, halves each pass. Integer division: for n=8, gaps are 4, 2, 1. For n=5, gaps are 2, 1. The loop exits when gap becomes 0.
Middle loop (i) — moves through the array from position gap to n-1. Each element arr[i] is the “key” to be inserted into its correct position within its gap-sublist.
Inner loop (j) — shifts elements rightward within the sublist while arr[j-gap] > temp. This is exactly insertion sort but with a stride of gap instead of 1. When the loop exits, j is the insertion position.
temp saves arr[i] — before the shifting begins, the key is saved in temp. The shifting overwrites arr[i], but temp holds the original value. This is the standard insertion-sort save-shift-place idiom.
const in print_array — the print function takes const int arr[] because it never modifies the array. Marking parameters const is good practice: it documents intent and prevents accidental writes.

Shell Sort Complexity and Comparison

Algorithm	Best case	Average case	Worst case	Stable?
Shell sort (n/2 gaps)	O(n log n)	O(n^1.25–n^1.5)	O(n²)	No
Bubble sort	O(n)	O(n²)	O(n²)	Yes
Insertion sort	O(n)	O(n²)	O(n²)	Yes
Merge sort	O(n log n)	O(n log n)	O(n log n)	Yes
Quick sort	O(n log n)	O(n log n)	O(n²)	No

Shell sort’s complexity depends on the gap sequence chosen. Better sequences (Hibbard: 1,3,7,15,…; Sedgewick: 1,5,19,41,…) achieve O(n^4/3) or better. The n/2 halving used here is the simplest and widely taught.

What This Program Teaches

Shell sort as layered insertion sort — the outermost loop over gap sizes turns the standard insertion sort into Shell sort with no other changes. Each pass uses a larger stride; when gap=1 the innermost logic is exactly insertion sort.
Gap sequence selection matters — the n/2 halving is simple but not optimal. This program teaches the concept; real applications often use Ciura’s empirical sequence (1,4,10,23,57,132,301,701) for best practical speed.
Passing arrays as pointers to functions — void shell_sort(int arr[], int n) and int arr[] is syntactic sugar for int *arr. The array decays to a pointer at the call site; changes inside the function affect the original array.
Why gets() is dangerous — the original post used gets(string), which has no bound on how many characters it reads. A long enough input overflows the buffer and corrupts memory. fgets(string, sizeof string, stdin) or scanf("%Ns", string) (where N is the buffer size minus 1) are the safe alternatives.

Related Programs

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.

C Program to sort the string, using shell sort technique.