Insertion Sort

O Insertion sort expande um prefixo ordenado. Ele remove o próximo valor, desloca para a direita os elementos maiores do prefixo e insere o valor no espaço resultante.

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;
    }
}

Antes da iteração i, o prefixo values[0..i) está ordenado e contém exatamente os elementos do prefixo original. A inserção preserva esse invariante. O melhor caso é Θ(n); os casos médio e pior são Θ(n²). O algoritmo usa espaço auxiliar Θ(1) e é estável.