An answer to this question on Stack Overflow.

Question

I am confused if these comparison numbers are supposed to be this large in value for a vector with 100 random two-digit numbers. Full program --> safe link: https://ideone.com/oybDbD The program output is at the bottom page of the link. Appreciate input.

int insertionSort (vector<int> &v) {
 	int j, temp, counter = 0;
    for (int i = 1; i < v.size(); i++) {
	    j = i;
	    while (++counter && j > 0 && v[j] < v[j-1]){
		    temp = v[j];
		    v[j] = v[j-1];
		    v[j-1] = temp;
		    j--;
	    }
	}
    return counter;
}

Answer

The average case performance of insertion sort is O(N^2) (see the wiki entry). For your vector of 100 elements, the expected number of comparisons is therefore O(10000). Coming out with 2656 or, in your second run, 4995, comparisons is therefore lower than you might otherwise expect.