This program illustrates insertion sort. Insertion sort is based on the idea of inserting records into an existing sorted file.  
                                  

insert (int a[], int n)
{
        int i,k,nw;
        /*the first entry is assumied to be sorted */
        for (k=1;k=0 && nw < a[i]; i--)
                        a[i+1]  =a[i];
                /*insert new key at its proper position*/
                a[i+1]=nw;
        } /*end of outer loop*/
}/*end of the routine*/