Insertion Sort

Insertion sort grows a sorted prefix. It removes the next value, shifts larger prefix elements right, and inserts the value into the resulting gap.

static void insertionSort(int[] values) {
    for (int i = 1; i < values.length; i++) {
        int current = values[i];
        int j = i - 1;
        while (j >= 0 && values[j] > current) {
            values[j + 1] = values[j];
            j--;
        }
        values[j + 1] = current;
    }
}

Before iteration i, the prefix values[0..i) is sorted and contains exactly the original prefix elements. Insertion preserves this invariant. The best case is Θ(n); average and worst cases are Θ(n²). The algorithm uses Θ(1) auxiliary space and is stable.