Running Time

Here is the abbreviated algorithm (again):

for (int j = 1; j < N; j++)
{
  loop: insert list[j] into its proper place in sub-list of size j
}

The first time the outer loop executes (with j=1), how many times does the inner loop execute its body?

If the first two integers are already in order, the inner loop does not execute even once. If the first two integers are out of order, the inner loop executes once, to perform one swap.

After a while, when j is a particular value, how many times does the inner loop execute its body?

This is hard to say. If the list is already in order (so you are sorting a sorted list) then the inner loop stops immediately. Nothing needs to be moved. But if the list is exactly backwards (so every new value must be moved all the way down the sub-list) then the inner loop executes j times, the size of the sub-list. On the average, you would expect the new integer to be moved halfway down the sorted sub-list, for j/2 moves.

In general, when looking at running times you need to examine the (i) Best Case, (ii) Worst Case, and (iii) Average Case. Let's look at the average case:

j (size of sorted sub-list)	1	2	3	4	...	N-2	N-1
average executions of inner loop	1/2	2/2	3/2	4/2	...	(N-2)/2	(N-1)/2

So the average total number of times the body of the inner loop is executed is

(1/2){ 1 + 2 + 3 + 4 + ... + (N-2) + (N-1) }

The total running time of the sorting method is proportional to this sum.

1 + 2 + 3 + 4 + 5 + ... + M = M*(M+1)/2

(1/2){ 1 + 2 + 3 + 4 + ... + (N-2) + (N-1) }