In the worst case, insertion sort takes on the characteristic of a quadratic function, which is to say there is a squared term in the total runtime T(n). First, let’s determine the cost and number of times each instruction takes. Some notes:
- a 1-based array
INSERTION-SORT(A) cost times for j = 2 to length[A] c1 n do key <- A[j] c2 (n-1) i <- j-1 c3 (n-1) // a comment 0 (n-1) while i>0 and A[i]>key c5 sum(j=2..n) t do A[i+1] <- A[i] c6 sum(j=2..n) t-1 i <- i-1 c7 sum(j=2..n) t-1 A[i] <- key c8 (n-1)
Each loop runs one more time as part of its “loop check” to exit: the for loop runs from 2 to n, which is (n-1) times, plus one additional time to exit. Most loops I write start from 1 or 0 to n or (n-1), and those would run n times plus 1, or (n+1), times.
The sum(j=2..n) notation is summation from 2 to n, where t is the number of times per term: when j=2, t=2; when j=3, t=3; and so on. This summation includes the extra once of checking the loop exit, which is the i>0 check. When j=5, i initializes to 4 and takes on the values 3,2,1 and 0: the zero is the loop check.
If t is the number of times the loop runs, the instructions within the loop runs one less time, or (t-1); that’s why the while body runs (t-1) times.
The constants are numbered from c1 to c8 to represent a definite time to execute that instruction. We multiply this constant by the number of times to get a term to describe the subtotal cost; then T(n) is the sum of all these subtotals.
The shortcut of calculating the summation sum(j=2..n) t is n*(n+1)/2 – 1, which yields the n-squared. So in the worst case of a reversed list of numbers, insertion sort would take time-squared of the input size.