Write InsertionTrace. Read n and n integers. First count the inversions of the input (pairs i < j with a[i] > a[j]). Then run insertion sort, printing the array after each pass and counting the element shifts and the key comparisons.
For the input
6
5 2 4 6 1 3
the program prints
pass 1: [2, 5, 4, 6, 1, 3]
pass 2: [2, 4, 5, 6, 1, 3]
pass 3: [2, 4, 5, 6, 1, 3]
pass 4: [1, 2, 4, 5, 6, 3]
pass 5: [1, 2, 3, 4, 5, 6]
Shifts: 9, inversions in the input: 9
Comparisons: 12 (best n-1 = 5, worst n(n-1)/2 = 15)
What do you notice about the number of shifts and the number of inversions?