// Requires (n + d) comparisons, where d is the number of inversions.
// An inversion is where you have two numbers at indices i and j (j > i)
// and list[i] > list[j].
// Stable algorithm - Given two instances of the same key in the list,
// those instances are in the same order in the sorted list as they were
// in the unsorted list.  Example: 2 2 4 1  - try with SelectionSort (not stable)
// Online - Can sort the list as it arrives (not required to hold entire list in memory).
// In-place - No extra memory required.
public class InsertionSort {
	public static void main(String[] args) {
		for (int i = 0; i < args.length; i++) {
			System.out.print(args[i] + " ");
		}
		System.out.println();
		doInsertionSort(args);
		System.out.println();
		for (int i = 0; i < args.length; i++) {
			System.out.print(args[i] + " ");
		}
	}
	
	public static void doInsertionSort(String[] list) {
		int comparisonCount = 0;
		for (int i = 1; i < list.length; i++) {
			String value = list[i];
			int j = i - 1;
			while (j >= 0 && list[j].compareTo(value) > 0) {
				comparisonCount++;
				list[j + 1] = list[j];
				j--;
			}
			comparisonCount++;
			list[j + 1] = value;
		}
		System.out.println("Sort performed with " + comparisonCount + " comparisons");
	}
}