# Algorithms Notes – Insertion Sort

Animation depicting insertion sort

The following is the source code for insertion sort:

for i = 1 to length(A) - 1
x = A[i]
j = i - 1
while j >= 0 and A[j] > x
A[j+1] = A[j]
j = j - 1
end while
A[j+1] = x
end for

Here is an implementation in C++ from Weiss’s book:

template void Insertion_Sort(Etype A[], const unsigned int N)
{
Etype Tmp;

A[0] = Min_Val();
for (int P = 0; P <= N; P++)
{
Tmp = A[P];
for (int j = P; Tmp < A[j-1]; j–)
A[j] = A[j-1];
A[j] = Tmp;
}
}
[/sourcecode]

Analysis:

Since it has nested loops which take at most $n$ iterations, insertion sort is $\mathcal{O}(n^2)$. This is a tight bound (a reverse order array as input can achieve this bound). To calculate the average case:

$\sum_{P = 2}^{n} = 2 + 3 + ... + n = \Theta(n^2)$.