Shell sort

Insertion sort done at a distance first: a shrinking gap moves far-out-of-place values close to home before the final, cheap pass.

Time O(n log n) to O(n²), gap dependentSpace O(1)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Shell sort runs insertion sort on subarrays made of elements that are a fixed gap apart, starting with a large gap and shrinking it toward 1. Early passes with a big gap move far-out-of-place elements close to where they belong in just a few shifts, so by the time the gap reaches 1 the array is nearly sorted and the final insertion-sort pass is cheap. It keeps the simplicity and in-place nature of insertion sort while fixing its weak spot on arrays where small values start near the end.

Code

public static void ShellSort(int[] a) {
    int n = a.Length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > temp) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp;
        }
    }
}

Tips

Knuth-style 3h+1 gap sequences beat the simple n/2 halving used here in practice.
Still can be O(n squared) for simple gap sequences, but in practice far faster than plain insertion sort.

In the .NET library

.NET does not ship a shell sort, but the gap idea shows up anywhere a cheap near-sort pass is wanted before a more exact, more expensive sort runs.