Insertion sort comparison?

Question

How to count number of comparisons in insertion sort in less than O(n^2) ?

Answer 1

When we're inserting an element, we alternate comparisons and swaps until either (1) the element compares not less than the element to its right (2) we hit the beginning of the array. In case (1), there is one comparison not paired with a swap. In case (2), every comparison is paired with a swap. The upward adjustment for number of comparisons can be computed by counting the number of successive minima from left to right (or however your insertion sort works), in time O(n).

num_comparisons = num_swaps
min_so_far = array[0]
for i in range(1, len(array)):
    if array[i] < min_so_far:
         min_so_far = array[i]
    else:
         num_comparisons += 1