The following is the source code for insertion sort:

fori = 1tolength(A) - 1 x = A[i] j = i - 1whilej >= 0 and A[j] > x A[j+1] = A[j] j = j - 1end whileA[j+1] = xend 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 iterations, insertion sort is . This is a tight bound (a reverse order array as input can achieve this bound). To calculate the average case:

.

Advertisements