public class InsertionSort {

    /** It sorts in non-decreasing order the first N positions of A. It uses 
        the insertion sort method.
    */
    public static void insertionSort(int a[]) {
        for (int limit = 1; limit < a.length; ++limit) {
        // In each iteration, the elements a[0].. a[limit-1] are in sorted order
  	    int who = a[limit];
	    int k = limit-1;
	    while (k>= 0 && a[k] > who) {
	    // who is equal to a[limit] and a[k+1]..a[limit-1] are all
	    // greater than who and have been shifted one place to the right
		a[k+1] = a[k];
		k--;
	    }
	    a[k+1] = who;
        }
    }

    /** Print out the array a */
    public static void printArray(int[] a) {
	for (int x: a)
	    System.out.print(x + "  ");
	System.out.println();
    }

    public static void main(String[] args) {
	int[] table = {7,3,5,8,2,1};
	printArray(table);
        insertionSort(table);
	printArray(table);
	System.exit(0);
    }
}