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).

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).