Shell sort

Insertion sort moves a small value at the end of the array only one cell per comparison. Watch what happens when it first moves values five cells at a time.

⋯7void gapped_insertion(int *a, int n, int gap)8{9    for (int i = gap; i < n; i++) {10        int x = a[i];11        int j = i - gap;12        while (j >= 0) {13            comparisons++;14            if (a[j] <= x)15                break;16            a[j + gap] = a[j];17            moves++;18            j -= gap;19        }20        a[j + gap] = x;21    }22}23 24void shell_sort(int *a, int n)25{26    for (int gap = n / 2; gap > 0; gap /= 2)27        gapped_insertion(a, n, gap);28}29 

Long jumps first

In insertion sort, a value moves one cell per comparison. A small value near the end of a long array needs many comparisons to reach the front. Shell sort first sorts the values that are a gap h apart: a[0], a[h], a[2h], …, then a[1], a[1 + h], …, each chain on its own. A small value then travels h cells per move. Then it does the same with a smaller gap, and finally with gap 1, which is an ordinary insertion sort.

An array whose chains h apart are all sorted is called h-sorted. The last pass, with gap 1, makes the array 1-sorted, which is sorted. The earlier passes only make that last pass cheap: by then most values are close to their places, and insertion sort’s cost is n − 1 plus the number of inversions left.

The code and its cost

void gapped_insertion(int *a, int n, int gap)
{
    for (int i = gap; i < n; i++) {
        int x = a[i];
        int j = i - gap;
        while (j >= 0) {
            comparisons++;
            if (a[j] <= x)
                break;
            a[j + gap] = a[j];
            moves++;
            j -= gap;
        }
        a[j + gap] = x;
    }
}

void shell_sort(int *a, int n)
{
    for (int gap = n / 2; gap > 0; gap /= 2)
        gapped_insertion(a, n, gap);
}

gapped_insertion is insertion sort with every 1 replaced by gap: x is compared with the value gap cells before it, a larger one moves gap cells right, and j steps back by gap. Taking i from gap to n − 1 in order sorts all the chains at once, one value of each in turn. shell_sort halves the gap: for ten values 5, 2, 1.

The ten values

After the gap-2 pass only 5 inversions are left, so the final insertion sort makes 5 moves. In all, shell-ten.c prints ten: 35 comparisons, 18 moves. Insertion sort alone makes 27 comparisons and 20 moves on the same values (Insertion sort): on ten values Shell sort compares more and moves only slightly less. The gaps pay off on larger arrays.

The gaps decide the cost

With gaps that halve, the worst case is still O(n²): if the gaps are all even until the last, values in odd cells are never compared with values in even cells until the final pass. Better sequences avoid that. One widely used rule takes gaps 1, 4, 13, 40, …, each 3h + 1, from the largest below n down to 1; measured on random input, its cost grows like about n^1.3. That figure comes from experiment, not from a proof, and the best sequence is still unknown.

Shell sort is in place and needs no recursion. It is not stable: a long move can carry a value past an equal one in another chain.

Worked example

A thousand values. shell.c also sorts the 1,000 values (i × 389) mod 1009, which are all different and scrambled, once with Shell sort and once with insertion sort alone. Shell sort makes 12,916 comparisons and 5,520 moves; insertion sort makes 251,837 comparisons and 250,838 moves, about 19 times as many comparisons and 45 times as many moves.

Two checks. What gaps does halving give for n = 20? (10, 5, 2, 1.) Why must the last gap be 1? (Only then is every pair of neighbours compared, so only then is the array sure to be sorted.)

Where it’s used

Small embedded programs. Where code size matters and recursion is unwelcome, Shell sort gives an in-place sort far faster than insertion sort on hundreds or thousands of values, in a dozen lines.

A step between the simple sorts and the fast ones. It shows that insertion sort’s weakness is short moves, which Merge sort and quicksort avoid by other means.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.