Fast version of insertion sort algorithm

insertionSort.cpp

static void insertionSort(int[] a) {
	for(int i = 1; i < a.length; ++i) {
		// invariant x[0:i-1] sorted
		// shift i_th element to its proper place
		for(int j = i; j > 0 && a[j-1] > a[j]; --j) {
			swap(a, j-1, j);
		}
	}
}
​
// faster
static void insertionSort(int[] a) {
	for(int i = 1; i < a.length; ++i) {
		int j = i;
		int t = a[j];
		while(j > 0 && a[j-1] > t) {
			a[j] = a[j-1];
			--j;
		}
		a[j] = t;
	}
}