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;


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).


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s