public void InsertionSort(int[] A) {
		// O(n^2)


		// basic idea:
		// there are "two" array in a single array A.
		// the first part of the array is sorted,
		// and the second part of the array is not sorted,
		// we scan from the head of the array, and determine
		// the right position for the current element.
		int i = 0, j = 0;
		for (i = 1; i < A.length; i++) {
			int current = A[i];
			for (j = i - 1; (j >= 0 && A[j] > current); j--) {
				A[j + 1] = A[j];
			}
			// the right place for current element
			A[j + 1] = current;
		}
	}