Shell Sort Algorithm

What is Shell Sort?

Shell Sort is an in-place comparison sort that generalizes Insertion Sort by allowing the exchange of items that are far apart. It improves performance by comparing and sorting elements at a defined gap (also called interval or stride), which decreases over time until the gap is 1 — effectively ending with a standard Insertion Sort.

Shell Sort is named after Donald Shell, who introduced it in 1959.

How Shell Sort Works

1. Choose a gap sequence (e.g., n/2, n/4, …, 1).
2. Sort elements that are gap distance apart using Insertion Sort logic.
3. Gradually reduce the gap and repeat the process.
4. Finish when the gap is 1.

Each pass moves elements closer to their correct position, so the final Insertion Sort becomes very efficient.

Key Properties

• In-place: No additional memory required.
• Not stable: Relative order of equal elements might change.
• Faster than Bubble, Insertion, and Selection Sort for medium-sized datasets.

Time & Space Complexity

• Space Complexity: O(1)

When to Use

• Great for moderate-sized arrays.
• When a simple, fast in-place sort is needed and stability is not required.
• Easy to implement and often faster than O(n²) algorithms.

Code Example

public class ShellSortExample {

    public static void shellSort(int[] arr) {
        int n = arr.length;

        // Start with a large gap, then reduce the gap
        for (int gap = n / 2; gap > 0; gap /= 2) {

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

                // Shift earlier gap-sorted elements up until correct location for arr[i] is found
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }

                // Put temp (original arr[i]) in its correct location
                arr[j] = temp;
            }

            // Print after each pass
            System.out.print("After gap " + gap + ": ");
            printArray(arr);
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {23, 12, 1, 8, 34, 54, 2, 3};
        System.out.println("Original array:");
        printArray(arr);

        shellSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output

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

Visual Explanation (Step-by-Step)

Let’s sort:

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

Step 1: Gap = 4

Compare and sort elements that are 4 positions apart:

• Compare 0 ↔ 4 → 23 vs 34 → OK
• Compare 1 ↔ 5 → 12 vs 54 → OK
• Compare 2 ↔ 6 → 1 vs 2 → OK
• Compare 3 ↔ 7 → 8 vs 3 → swap → 3 moves before 8

After pass:

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

Step 2: Gap = 2

Now compare elements 2 apart:

• Compare 0 ↔ 2 → 23 vs 1 → swap
• Compare 2 ↔ 4 → 23 vs 2 → swap
• Compare 4 ↔ 6 → 23 vs 12 → swap
• Compare 6 ↔ 8 → (out of bounds)

Array becomes:

[1, 3, 2, 8, 12, 54, 23, 34]
→ refined again →
[1, 3, 2, 8, 12, 23, 34, 54]

Step 3: Gap = 1

Final Insertion Sort-like pass:

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

Final Sorted Array

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

Summary

• Shell Sort is a clever extension of Insertion Sort that allows swapping far-apart elements first.
• It’s faster than quadratic sorts like Bubble or Selection, especially with a good gap sequence.
• In-place and simple, making it a good fit for certain performance-critical applications.