Insertion Sort

To explain this method of sorting, I would take the example of playing cards.It's like we have a card in left hand and all other cards lie on the table. We pick one of the cards lying on the table and compare with the one in our hand and place it ahead or behind it. This way what we will get is a sorted list of 2 in our hand. And now if we pick another card from the table and place it in its proper sorted position in the cards in our hand, we will have again a sorted list in our hand which is incrementing one at a time at its position only. So insertion sort is one simple way of sorting.
Like we have numbers given as : 8 3 2 1 5
The first element is assumed to be sorted and serve as the one against which comparison making will be started as explained earlier in the case of playing cards, this would serve as the first card in the left hand.

First Pass :  would scan second element and will put it at its right position, doing comparisons with the element earlier to it.
                                                 3 8 2 1 5

Second Pass : Scans the third element , compare with 2 elements before it and find its place.
                       3 8 2 1 5 = = = =  3 2 8 1 5  = = = =  2 3 8 1 5

Third Pass :    2 3 8 1 5 = = = = 2 3 1 8 5 = = = = 2 1 3 8 5 = = = = 1 2 3 8 5

Fourth Pass : 1 2 3 8 5 = = = = 1 2 3 5 8

The array goes sorted.

Try following cpp code

#define MAX 10
#include<iostream>
using namespace std;
int main()
{
    int arr[MAX];
    int i,j,temp;
    for(i=0;i<MAX;i++)
    {
        cout<<"\n enter the element ["<<i+1<<"]: : ";
        cin>>arr[i];
    }

    for(j=1;j<MAX;j++)
    {
        i=j-1;
        temp=arr[j];
        while(i>=0 && temp<arr[i])
        {
            arr[i+1]=arr[i];
            i--;
           
        }
        arr[i+1]=temp;
    }
            cout<<"\n ********* SORTED ARRAY INSERTION SORT ********* \n \n ";

    for(i=0;i<MAX;i++)
    {
        cout<<"\n element ["<<i+1<<"] is ";
        cout<<arr[i];
    }
getchar();
getchar();

}

to see an output like

Output for code above

For Insertion sort the worst-case running time is θ(n2), and the best-case running time is θ(n).
Insertion sort uses no extra memory, it sorts in place.