public class InsertionSort {

	/* Direkte oversetting av algoritmen på side 17 i læreboken
	   fra pseudokode til Java.
	   Legg spesielt merke til at indeksene i og j er flyttet
	   ett hakk nedover fordi arrayene i boken begynner indeksene
	   på 1 mens man i Java begynner på 0.
	*/
	static void Sort(int[] A) {
		for (int j=1; A.length>j; ++j) {
			int key = A[j];
			// Insert A[j] into the sorted sequence A[0..j-1].
			int i = j-1;
			while (i>=0 && A[i]>key) {
				A[i+1] = A[i];
				--i;
			}
			A[i+1] = key;
		}
	}

	/* Resten av programmet er uinteressant */

	public static void main(String[] args) {
		int[] testtall = {3, 5, 1, 3, 17, 14, 8, 1, 12};
		print(testtall);
		Sort(testtall);
		print(testtall);
	}

	static void print(int[] A) {
		for (int i=0; A.length>i; ++i)
			System.out.print(A[i]+" ");
		System.out.println();
	}

}