Shell Sort Algorithm

What is Shell Sort?

Shell Sort is an optimized version of Insertion Sort. It improves upon the basic insertion sort by allowing the exchange of far-apart elements, which helps reduce large-scale disorder faster. Named after its inventor Donald Shell, this algorithm is especially useful for medium-sized arrays.

Shell Sort works by sorting elements that are a certain gap apart, then progressively reducing the gap until it becomes 1 (at which point it finishes with a final insertion sort).

How Shell Sort Works

1. Start with a gap (typically n/2) and perform a gapped insertion sort.
2. Reduce the gap (e.g., divide by 2 or use a custom sequence).
3. Repeat the process until the gap is 1, where it acts like a standard insertion sort but with elements already nearly sorted.

By moving elements over large gaps early on, Shell Sort drastically reduces the total number of swaps needed in the later stages.

Time and Space Complexity

• Space Complexity: O(1) (in-place)
• Stable: ❌ No (equal elements may change order)

Shell Sort’s performance heavily depends on the gap sequence used. Common sequences include:

• Shell’s original: n/2, n/4, ..., 1
• Hibbard’s, Sedgewick’s, and Pratt’s sequences for better performance

When to Use Shell Sort

• When you need an in-place, easy-to-implement sort with better performance than Bubble/Insertion Sort
• When sorting medium-sized arrays
• When stability is not required

Shell Sort – C++ Code Example

#include <iostream>
using namespace std;

void shellSort(int arr[], int n) {
    // Start with a large gap, reduce it each iteration
    for (int gap = n / 2; gap > 0; gap /= 2) {

        // Perform gapped insertion sort for this gap
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;

            // Shift earlier elements until the right position for arr[i]
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }

            // Place temp at its correct location
            arr[j] = temp;
        }

        // Print array after each gap reduction
        cout << "After gap " << gap << ": ";
        for (int k = 0; k < n; k++) cout << arr[k] << " ";
        cout << endl;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {23, 12, 1, 8, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array:\n";
    printArray(arr, n);

    shellSort(arr, n);

    cout << "Sorted array:\n";
    printArray(arr, n);

    return 0;
}

Output

Original array:
23 12 1 8 34 54 2 3 
After gap 4: 3 12 1 8 23 54 2 34 
After gap 2: 1 2 3 8 23 12 34 54 
After gap 1: 1 2 3 8 12 23 34 54 
Sorted array:
1 2 3 8 12 23 34 54 

Shell Sort – Visual Explanation (Step-by-Step)

Let’s sort:

[23, 12, 1, 8, 34, 54, 2, 3]

Step 1: Gap = 4

Compare elements 4 apart:

• Compare 23 and 34 → OK
• Compare 12 and 54 → OK
• Compare 1 and 2 → OK
• Compare 8 and 3 → Swap → [23, 12, 1, 3, 34, 54, 2, 8]

After inserting:

[3, 12, 1, 8, 23, 54, 2, 34]

Step 2: Gap = 2

Compare elements 2 apart:

• Compare 3 and 1 → Swap
• Compare 12 and 8 → Swap
• Compare 1 and 2 → OK
• Compare 8 and 34 → OK

After inserting:

[1, 2, 3, 8, 23, 12, 34, 54]

Step 3: Gap = 1 (Final pass)

Now it works like regular Insertion Sort, but the array is mostly sorted already.

• Insert 2 → OK
• Insert 3 → OK
• Insert 8 → OK
• Insert 12 (move 23)
• Final result:

[1, 2, 3, 8, 12, 23, 34, 54]

Final Sorted Array

[1, 2, 3, 8, 12, 23, 34, 54]

Summary

• Shell Sort improves insertion sort by allowing exchanges of distant elements early on.
• It performs better than quadratic algorithms like Bubble and Insertion Sort.
• It is in-place but not stable.
• Its performance is influenced by the gap sequence used.