Shell sort in C: solved exercise step by step

Shell sort method in C

If you are looking for a shell sort in C solved exercise, this post explains the full logic, not just the final code.

Shell sort improves insertion sort by using gaps. Instead of comparing only adjacent values, it compares values that are farther apart and progressively reduces the gap until it reaches 1. It is an in-place algorithm and often performs better than bubble sort or insertion sort on medium-sized arrays.

Problem statement

Implement shell sort to sort an integer array in ascending order.

C solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>

void shell_sort(int a[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int tmp = a[i];
            int j = i;

            while (j >= gap && a[j - gap] > tmp) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = tmp;
        }
    }
}

int main(void) {
    int a[] = {29, 10, 14, 37, 13, 5, 42, 8};
    int n = (int)(sizeof(a) / sizeof(a[0]));

    shell_sort(a, n);

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

Expected output

1

5 8 10 13 14 29 37 42

Common mistakes

  • Reducing gap incorrectly and causing infinite loops.
  • Forgetting the temporary value (tmp) before shifting values.
  • Using a wrong while condition and overwriting data.
  • Assuming fixed complexity: runtime depends on the chosen gap sequence.

Practical use

Shell sort is useful when:

  • you want a simple implementation,
  • you need better average behavior than insertion sort with low memory overhead,
  • you are practicing sorting techniques before moving to more advanced algorithms.

Guided practice and full book

If you want a complete path with progressive difficulty:

FAQ

Is shell sort better than insertion sort in C?

In many practical scenarios, yes. Large initial gaps reduce disorder early and make the final pass cheaper.

What is shell sort complexity?

It depends on the gap sequence. With basic n/2 gaps, worst-case behavior can approach O(nĀ²), but practical results are often better than insertion sort.

How should I practice shell sort effectively?

Trace two passes manually (gap = n/2 and gap = n/4) and compare the number of shifts with insertion sort on the same input.