Shell Sort Algorithm in DSA C++

Mental Model

Shell sort improves simple sorting by comparing elements far apart first, then gradually reducing the gap to sort closer elements.

Analogy: Imagine organizing books on a shelf by first sorting every 4th book, then every 2nd book, and finally sorting all books one by one to get a fully ordered shelf.

Array: [8, 5, 3, 7, 6, 2, 4, 1]
Gap = 4 -> Compare elements 4 apart
Indexes: 0    1    2    3    4    5    6    7
Values:  8 -> 5 -> 3 -> 7 -> 6 -> 2 -> 4 -> 1

Dry Run Walkthrough

Input: array: [8, 5, 3, 7, 6, 2, 4, 1]

Goal: Sort the array in ascending order using Shell sort by reducing gap and sorting subarrays.

Step 1: Start with gap = 4, compare and sort elements 4 apart

[6, 5, 3, 7, 8, 2, 4, 1]

Why: Swapped 8 and 6 because 6 < 8 to partially sort distant elements

Step 2: Continue gap = 4, compare and sort elements 4 apart

[6, 1, 3, 7, 8, 2, 4, 5]

Why: Swapped 5 and 1 because 1 < 5 to improve order

Step 3: Reduce gap to 2, sort elements 2 apart using insertion sort

[3, 1, 4, 2, 6, 5, 8, 7]

Why: Sorting closer elements to refine order

Step 4: Reduce gap to 1, final insertion sort pass

[1, 2, 3, 4, 5, 6, 7, 8]

Why: Final pass to fully sort the array

Result:

[1, 2, 3, 4, 5, 6, 7, 8]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // gap reduces each iteration
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            // insertion sort for elements gap apart
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

int main() {
    vector<int> arr = {8, 5, 3, 7, 6, 2, 4, 1};
    shellSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

for (int gap = n / 2; gap > 0; gap /= 2) {

reduce gap size each iteration to sort elements closer together

for (int i = gap; i < n; i++) {

iterate over elements starting from gap index

while (j >= gap && arr[j - gap] > temp) {

shift elements greater than temp to the right to insert temp in correct position

arr[j] = temp;

insert temp at its correct sorted position within the gap-sorted subarray

Output

1 2 3 4 5 6 7 8 

Complexity Analysis

Time: O(n^(3/2)) on average because gap sequence reduces comparisons and shifts compared to simple insertion sort

Space: O(1) because sorting is done in place without extra arrays

vs Alternative: Faster than insertion sort (O(n^2)) for larger arrays by sorting distant elements first to reduce total shifts

Edge Cases

empty array

function returns immediately without changes

DSA C++

for (int gap = n / 2; gap > 0; gap /= 2) {

array with one element

array remains unchanged as it is already sorted

DSA C++

for (int gap = n / 2; gap > 0; gap /= 2) {

array with all elements equal

no swaps occur, array remains the same

DSA C++

while (j >= gap && arr[j - gap] > temp) {

When to Use This Pattern

When you need a faster version of insertion sort that works well on medium-sized arrays, use Shell sort because it reduces total shifts by sorting elements far apart first.

Common Mistakes

Mistake: Not reducing the gap correctly by dividing by 2 each iteration
Fix: Use gap /= 2 in the outer loop to gradually reduce gap size

Mistake: Incorrectly shifting elements inside the inner while loop causing infinite loops
Fix: Ensure j is decremented by gap each time inside the while loop to move backwards properly

Summary

Shell sort sorts an array by comparing elements far apart and gradually reducing the gap to fully sort.

Use Shell sort when you want a simple, in-place sorting faster than insertion sort for medium arrays.

The key insight is sorting distant elements first reduces the total work needed for final sorting.