Insertion sort

Invariant: at the start of iteration i, arr[0..i-1] is sorted (it holds the original first i elements in order). Inserting arr[i] into that prefix extends the invariant to arr[0..i].

When i reaches n, the whole array is sorted. This is a textbook example of proving correctness with a loop invariant: it holds at initialisation, each iteration maintains it, and it gives the result at termination.

1public static void insertionSort(int[] arr) {
2    for (int i = 1; i < arr.length; i++) {
3        int key = arr[i];
4        int j = i - 1;
5        while (j >= 0 && arr[j] > key) {
6            arr[j + 1] = arr[j];          // shift right
7            j--;
8        }
9        arr[j + 1] = key;
10    }
11}

Hold the key in a variable and shift larger elements one slot right with a single write each, then drop the key into the gap. That is one write per moved element plus one for the key.

The swap version (gnome sort, in 17.05) does three writes per step. The comparisons are the same, but shifting moves less data.

1// swap version: three writes per step
2for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
3    int tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp;
4}
5
6// shift version: one write per step
7int key = arr[i], j = i - 1;
8while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
9arr[j + 1] = key;

Each shift fixes exactly one inversion, so the total work is O(n + I), where I is the number of inversions. Sorted input has I = 0 and needs n - 1 comparisons. Reverse sorted input has I = n(n-1)/2.

This is why TimSort and introsort hand small or nearly sorted runs to insertion sort.

The loop condition arr[j] > key stops at an equal element, so the key is placed after existing equal keys and their order is preserved. Using >= would move the key past its equals and break stability.

Since the prefix is sorted, binary search can find the insert position in O(log i) comparisons. Use the upper-bound form (<=) so equal keys stay stable.

Comparisons fall to O(n log n) overall, but shifting is still O(n²) in the worst case. It helps when comparisons are expensive, for example comparing long strings or objects.

1public static void binaryInsertionSort(int[] arr) {
2    for (int i = 1; i < arr.length; i++) {
3        int key = arr[i];
4        int lo = 0, hi = i;
5        while (lo < hi) {                  // upper bound in arr[0..i)
6            int mid = (lo + hi) >>> 1;
7            if (arr[mid] <= key) lo = mid + 1;
8            else hi = mid;
9        }
10        System.arraycopy(arr, lo, arr, lo + 1, i - lo);
11        arr[lo] = key;
12    }
13}