prerequisites:

• http://chineseruleof8.com/code/index.php/2017/10/11/insertion-sort/
• https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/analysis-of-insertion-sort

Given

Say we’re at the last element with the number 0:

[ 2, 3, 5, 7, 11, (0) ]

In order for 0 to be sorted, it must be compared to 11. Since 11 is larger is needs to slide over 1. This goes for all elements.
Thus, every element in the array has to slide over one position to the right. Then 0 gets inserted into arr[0]…ending up with [0, 2, 3, 5, 7, 11]

If we’re inserting element n into array with k elements, we use c to denote the # of lines of code to test an element (i.e 0) against an element and slide the element over.

For example, something like this:

then c in our case is 2 operations. But nevertheless, for implementation independent, c will simply denote the # of operations it takes to do the comparison and move the element over.

Thus, it took c * k to slide k elements over in place so that [X, 2, 3, 5, 7, 11] and finally we can insert 0 at the beginning [0, 2, 3, 5, 7, 11].

Worst case scenerio

Suppose that upon every call to insert, the value being inserted is less than every element in the subarray to its left.

Say we have [8, (5), 2, 1]

Insertion sort says, we always start index 1 (which is 5) and compare with previous element. We put 5 in a tmp variable and do a comparison, 5 < 8, so we slide over 8 over. This takes c steps and we do this 1 time. [8,8,2,1]

Then insert 5 at arr[0]

[5,8,2,1]

Then we move on to index 2, which is number 2.

[5,8,(2),1]

We do a comparison, 2 < 8, so we slide 8 over .. this is c. [5,8,8,1]

Then we compare 2 < 5, and we slide 8 over .. this is c. [5, 5, 8, 1]

Now we’re at index 0, so we simply fill it with our element 2.

[2,5,8,1]

So this is c * 2.

Then we move on to index 3, which is number 4.
We do the same comparison, and up with c * 3. Because we compare and move 1 step 3 times.

c * 1 + c * 2 + c * 3 executions.

Let’s say we start off with array [8, 7, 6 , 5, 4, 3, 2, 1]
We start at index 1 as stated by Insertion sort.

Then we work on 7. We compare and move (c) for k(1) element. So that’s c * 1. We get [7 8 6 5 4 3 2 1]
Then we work on 6. We compare and move twice for 8 and 7. So that’s c * 2. We get [6 7 8 5 4 3 2 1]
Then we work on 5. We compare and move for three times for 8 7 5. So that’s c * 3. We get [5 6 7 8 4 3 2 1]

And so on, up through the last time, when k = n-1 where n is the # of total elements.

Notice n-1. Why is that? Because we do not do compare element at index 1. We start at index 1.

Thus, what you get is:
c * 1 + c * 2 + c * 3 + c * 4 .. c * (n-1) = c(1+2+3+4…n-1)

That sum is an arithmetic series, except that it goes up to n-1, rather than n.

Arithmetic Series – Summation

Now let’s use Arithmetic series to simply and prove it.

To find the sum of the 1st n terms of an arithmetic sequence:

S = n (a initial + a of n) / 2

where n is # of terms
a initial = first term
a of n = last term

Given 5 10 15 20, let’s calculate the number of elements:

20 (last value) – 5 (first value) = 15
15 / 5 = 3
3 + 1 = 4. Add 1 to the total terms due to initial value 5.

The sum of these 4 terms are:

S = 4 (5 + 20)/2 = 2 (25) = 50
check it: 5 + 10 + 15 + 20 = 50 √

Given 2 4 6 8 10 12 14 16 18 20

S = 10 (2 + 20) / 2 = 5 (22) = 110
if you add it on the calculator, its 110 √

Say we want to go further say 2 to 222
222 – 2 = 220
220 / 2 = 110
110 + 1 = 111 Don’t forget to add 1 to 110 due to our initial value 2.
S = 111 (2 + 222)/2 = 12,432

We can also calculate term at n

A at n = initial a + (n-1)d

say we get 5 10 15 20 25

We want to figure out the 3rd term

2nd term = 5 + (2-1)(5) = 10 √
3rd term = 5 + (3-1)(5) = 15 √
5th term = 5 + (5-1)(5) = 25 √
…
…
100n term = 5 + (100-1)(5) = 500 √

The Proof

Using our formula for arithmetic series, we get that the total time spent inserting into sorted subarrays is

S = n (a initial + a of n) / 2

where # of terms n is n – 1 (remember, we don’t do the comparison for the place where we insert the value)
initial a is c * 1
last term a is c * (n – 1)

Thus, given:

c * 1 + c * 2 + c * 3 + c * 4 .. c * (n-1) =
c(1+2+3+4…n-1)

total # of terms = n-1
initial a = c*1
last term = c*(n-1)

Now we plug in everything:

S = (total # of terms) ( initial a + last term a ) / 2
S = (n-1)(c*1 + c*(n-1))/2
S = c * (n-1)(1 + n – 1) / 2
S = (c*n*(n-1)) / 2 = (cn^2)/2 – cn/2

Using O notation, we discard lower order cn/2, which leaves us (cn^2)/2
We also leave constants so we get rid of c and 1/2, which leaves us n ^ 2. Therefore, O(n^2)

Can we do it faster?

The answer is yes. Suppose we have the array [2, 3, 5, 7, 11], where the sorted subarray is the first four elements, and we’re inserting the value 11.

Upon the first comparison at index 1, we see that 3 > 2. So no need to shift. That’s c * 1.
Then we go to index 2. We see 5 > 2. So no need to shift. That’s c * 1.
This goes for 5, 7, and finally 11.

These are all constants time. Because there are n-1

This is c * (n-1), which is O(n)

So under the best case of already sorted elements, we can do O(n)

Running time of Random elements

Suppose that the array starts out in a random order. Then, on average, we’d expect that each element is less than half of the # of elements to its left. This means we expect c * (1 + 2 + 3 + … + n-1 ) / 2

The running time would be half of the worst-case running time. But in asymptotic notation, where constant coefficients don’t matter, the running time in the average case would still
be O(n^2).

Almost Sorted

What if you knew that the array was “almost sorted”: every element starts out at most some constant number of positions, say 17, from where it’s supposed to be when sorted? Then each call to insert slides at most 17 elements, and the time for one call of insert on a subarray of k elements would be at most c * 17.

Over all n-1 calls to insert, the running time would be at most 17 * c * (n-1).

which is O(n) just like the best case. So insertion sort is fast when given an almost-sorted array.