Shell Sort

An in-place generalization of insertion sort that improves performance by comparing elements far apart using gap-based passes, achieving sub-quadratic time in practice.

Algorithms

Context

Shell Sort is an in-place comparison sort that improves upon insertion sort by allowing exchanges between elements that are far apart.

Insertion sort performs well on nearly sorted arrays but performs poorly (O(n²)) when elements must travel long distances. Shell Sort addresses this weakness by first partially sorting the array using large “gaps” between compared elements. As the gap shrinks, the array becomes increasingly ordered, making the final insertion pass efficient.

The algorithm works by repeatedly performing gapped insertion sorts, gradually reducing the gap until it becomes 1. When h = 1, the array is almost sorted, and the final insertion pass completes quickly.

Shell Sort does not have a single fixed time complexity — its performance depends heavily on the chosen gap sequence. With good increment sequences, it performs significantly better than quadratic sorts in practice.

Core idea

Shell Sort relies on three principles:

Choose a decreasing gap sequence (h).
For each gap h, perform an insertion sort on elements spaced h apart.
Reduce h until it reaches 1.

A common gap sequence is the Knuth sequence: h = 3h + 1
Example: 1, 4, 13, 40, 121, …

For each h:

Treat the array as h interleaved subarrays.
Perform insertion sort within each of those subarrays.
Reduce disorder progressively before the next, smaller gap.

Key insights:

Large gaps move elements long distances early.
Smaller gaps refine local order.
The final pass (h = 1) runs fast because the array is already partially sorted.
The algorithm is not stable.
It is in-place (O(1) extra memory).

Implementation

class ShellSort {
    static <T> void sort(Comparable<T>[] input) {
        int n = input.length;
        
        int h = 1;
        // computes the increment sequence
        while (h < n / 3) h = 3 * h + 1; 
        
        while (h >= 1) {
            for (var i = h; i < n; i++) {
                // insertion sort with h-step
                for (var j = i; j >= h && less(input[j], input[j - h]); j -= h) {
                    swap(input, j, j - h);
                }
            }
        
            h /= 3; // moves to the next increment
        }
    }   
    
    @SuppressWarnings("unchecked")
    private static <T> boolean less(Comparable<T> a, Comparable<T> b) {
        return a.compareTo((T) b) < 0;
    }
    
    private static <T> void swap(Comparable<T>[] input, int a, int b) {
        var temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }
}