# Insertion Sort

## Algorithm (sentinel)

```A[0] = -inf for i = 2 to n do t = A[i] j = i-1 while t < A[j] do A[j+1] = A[j] j = j-1 A[j+1] = t```

## Comparisons

All comparisons occur in the while loop.

For the best case, the while loop never actually executes, requiring $n-1$ comparisons.

For the worst case, the while loop executes until reaching the sentinel every time (reverse sorted).

• $\underset{i=1}{\overset{n}{\Sigma }}i$
• $=\frac{\left(n-1\right)\left(n+2\right)}{2}$

The average case requires calculating the expected value. The outer summation with index $i$ represents the for loop and the summation with index $j$ calculates the expected value of comparisons for all possible elements $A\left[i\right]$. Since $A\left[i\right]$ is equally likely to land anywhere in the subarray $A\left[1\dots i\right]$, take the expected value over all those possible positions.

• $\underset{i=2}{\overset{n}{\Sigma }}\underset{j=1}{\overset{i}{\Sigma }}\left(\frac{1}{i}\right)\left(i-j+1\right)$
• $=\frac{\left(n-1\right)\left(n+4\right)}{4}$

## Exchanges

For the purposes of this analysis we will also count the sentinel assignment.

For the best case, you only move to the temporary variable $t$ and then move back to the array. This requires $2n-1$ exchanges.

For the worst case, you must move every sorted element. Instead of calculating a summation we can see there’s a relationship between comparisons in the worst case and moves. Inside the for loop we do one more move than comparison.

• $\frac{\left(n-1\right)\left(n+2\right)}{2}+\left(n-1\right)+1$
• $=\frac{\left(n-1\right)\left(n+2\right)}{2}+n$

For the average case, we use apply the same relationship technique.

• $\frac{\left(n-1\right)\left(n+4\right)}{4}+\left(n-1\right)+1$
• $=\frac{\left(n-1\right)\left(n+4\right)}{4}+n$

## Algorithm (no sentinel)

```for i = 2 to n do t = A[i] j = i-1 while j > 0 and t < A[j] do A[j+1] = A[j] j = j-1 A[j+1] = t```

## Comparisons

All comparisons occur in the while loop. We don’t count the boundary check as an extra comparison even if it would take time in real life.

For the best case, the while loop never actually executes, requiring $n-1$ comparisons.

For the worst case, the while loop executes until reaching the edge of the array every time (reverse sorted).

• $\underset{i=1}{\overset{n}{\Sigma }}\left(i-1\right)$
• $=\frac{\left(n-1\right)n}{2}$

The average case is equivalent to the non-sentinel version except we do no sentinel comparisons. Therefore, if we can calculate the average number of sentinel comparisons, we have our answer.

• $\underset{i=2}{\overset{n}{\Sigma }}\frac{1}{i}$
• $={H}_{n}-1$

Therefore, the total comparisons is $\frac{\left(n-1\right)\left(n+4\right)}{4}-{H}_{n}+1$.

## Exchanges

This is not affected by the sentinel at all.