I have had the following problem at my last exam:
For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons.
My thinking was: there must be exactly one inversion of succeeding elements so any of the pairs (2, 3) or (3, 4) ... or (n-1, n) has to be swapped in the sorted sequence. So I answered n-2 because there's n-2 such pairs. But the answer was 2(n-1). Why?