class InsertionSort {
    class Node {
	public int key;
	public Object value;
    }

    public static void sort(Node[] arr) {
	for (int i = 1; i <= arr.length; i++) {
	    for (int j = i; j >= 0; j--) {
		if (arr[j].key >= arr[j-1].key) {
		    Node tmp = arr[j];
		    arr[j] = arr[j - 1];
		    arr[j] = tmp;
		}
	    }
	}
    }
}