Complexity
Best situation: the data is already sorted. The inner loop is never executed, and the outer loop is executed n – 1 times for total complexity of O(n).
Worst situation: data in reverse order. The inner loop is executed the maximum number of times. Thus the complexity of the insertion sort in this worst possible case is quadratic or O(n2).