Shell Sort

Shell sort

Shell sort extends direct insertion sort. Insertion needs less work when most items are already ordered: fewer comparisons and movements are necessary.

Can preprocessing make much of an array ordered? Grouping lets us make a rough adjustment first.

Consider {5,8,6,3,9,2,1,7}. Initially group pairs of items whose indices differ by half the array length.

Sort each group independently with insertion sort. The groups are small, so this requires little work. A few exchanges improve overall order and reduce the later insertion work.

We can continue by shrinking the distance between grouped items and repeating the process.

For the same eight-item sequence:

Donald Shell invented the algorithm. The distances are called increments or gaps. Many gap sequences are possible; Shell's original proposal repeatedly halves the gap.

Algorithm analysis

Grouping can reduce the work of insertion sort, giving better average performance than quadratic time for suitable inputs and gap sequences. In some extreme cases, the halving sequence still has a worst case of $O(n^2)$ and can even run slower than insertion sort.

For {2,1,5,3,7,6,9,8}, neither gap 4 nor gap 2 produces exchanges. Only gap 1 lets direct insertion adjust the array.

Here Shell sort adds grouping overhead without reducing insertion's work.

The halving gaps form a geometric sequence with blind spots. Other sequences, notably Hibbard and Sedgewick increments, address this issue.

Hibbard increments

The sequence is $1,3,7,15,\ldots$, with formula $2^i-1$.

The corresponding worst-case bound is $O(n^{3/2})$.

Sedgewick increments

The sequence is $1,5,19,41,109,\ldots$, combining $9\times4^i-9\times2^i+1$ and $4^{i+2}-3\times2^{i+2}+1$.

The corresponding worst-case bound is $O(n^{4/3})$.

These worst-case upper bounds have mathematical proofs. Average-case behavior and other gap sequences still include questions that are not fully resolved.

typedef int T;

typedef struct argument_t {
    T *data;
    int n;
} argument_t;

void *shell_sort_v1_0(void *args) {
    argument_t *arg = (argument_t *)args;
    T *arr = arg->data;
    int n = arg->n;

    int gap = n / 2;

    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            T temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }

    return arr;
}