Insertion Sort Algorithm

Insertion Sort is one of the simplest sorting algorithm.It is efficient algorithm for small number of inputs.

(Actually, as it is mentioned in MIT OpenCourseWare , till 30 element it will be efficient with comparing to Merge Sort).

Insertion Sort algorithm;
Efficiency is O(n^2). “(theta n^2)”
Worst case is input reverse ordered.
Best case is input ordered already.

Insertion sort algorithm example can be given as card game. When are starting with empty hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each cards already in the hand.

Another example; (by taking each element in order…)

Original 34 8 64 51 32 21
1st      8 34 64 51 32 21
2nd      8 34 64 51 32 21
3rd      8 34 51 64 32 21
4th      8 32 34 51 64 21
5th      8 21 32 34 51 64

Here is the C++ code ;