import java.util.Arrays;

public class InsertionSort {

    /**
     * Der klassische Insertion-Sort.
     * 
     * @param numbers
     *            diese ganzen Zahlen werden aufsteigend sortiert.
     */
    public static void sort(int[] numbers) {
        for (int len = 1; len < numbers.length; len++) {

            // Suche das erste Element das grösser ist als numbers[len]
            for (int i = 0; i < len; i++) {
                if (numbers[i] > numbers[len]) {
                    // Dann sind wir fertig und fügen numbers[len] an der
                    // Stelle i ein
                    insert(numbers, i, numbers[len], len);
                    break;
                }
            }
            // jetzt sind len+1 Elemente sortiert
        }
        assert isOrdered(numbers);
    }

    /**
     * Füge ein Element in ein Präfix eines Arrays ein.
     * 
     * @param numbers
     *            in dieses Array wird eingefügt.
     * @param index
     *            an dieser Stelle wird eingefügt, die nachfolgenden Elemente
     *            bis (exklusive) <code>len</code> werden um eins nach hinten
     *            verschoben.
     * @param element
     *            der einzufügende Wert.
     * @param len
     *            Länge des Präfixes. Alle elemente vor <code>len</code> (und ab
     *            <code>index</code>) werden verschoben, element <code>len</code> selbst
     *            wird überschrieben.
     */
    private static void insert(int[] numbers, int index, int element, int len) {
        assert index < len && len < numbers.length;
        for (int i = len; i > index; i--) {
            numbers[i] = numbers[i - 1];
        }
        numbers[index] = element;
    }

    public static void main(String[] args) {
        int[] numbers = { 3, 4, 3, 2, 1 };
        System.out.println("Davor: " + Arrays.toString(numbers));
        sort(numbers);
        System.out.println("Danach: " + Arrays.toString(numbers));
    }

    //---------------------- Prädikate für Assertions 

    public static boolean isOrdered(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (!(a[i] <= a[i + 1])) {
                return false;
            }
        }
        return true;
    }
}