InsertionSort

package Sort;

import java.util.Scanner;

public class InsertionSort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] arr = new int[in.nextInt()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.nextInt();
        }
        insertionSort(arr);
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    static void insertionSort(int arr[])
    {
        /*
            Começa a percorrer o array iniciando pela segunda casa e
            continua até acabar o array.
        */
        for (int i = 1; i < arr.length; ++i) {
            //Armazena o que está na casa atual.
            int key = arr[i];
            //Pega a posição imediatamente antes desta casa
            int j = i - 1;
            /*
                Continua caso o J sejá maior ou igual a zero e o array na posição j
                seja menor ou igual ao que está armazenado.
            */
            while (j >= 0 && arr[j] > key) {
                /*
                    Faz com que a posição a frente do j receba o que estiver em j
                    e faz o j decrescer. Isto continua até achar a posição onde
                    o valor armazenado deve ser posto ou quando o j for 0.
                */
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            //Põe o valor armazenado na posição certinha.
            arr[j + 1] = key;
        }
    }
}