Insertion sort (4)
Analysis (counting comparisons):
Let n = right – left + 1 be the length of the array.
Step 1.2 performs between 1 and r – left comparisons,say (r – left + 1)/2 comparisons on average.This is repeated with r = left+1, left+2, …, right.
Average no. of comparisons = 2/2 + 3/2 + … + n/2 = (n – 1)(n + 2)/4 = (n2 + n – 2)/4
Time complexity is O(n2).