In insertion sort the array is split into two sub-list sorted sub-list and unsorted sub-list. Values from the unsorted sub-list are picked and placed at the correct position in the sorted sub-list.

Example

//Insertion sort
#include<iostream>
using namespace std;
void insertsort(int arr[],int n) /* function to sort an arrayy with insertion sort */
{
int i,j,temp,found=0;
for (i=1;i<n;i++)
{
temp=arr[i];
j=i-1;

while(j>=0&&arr[j]>temp)
{
arr[j+1]=arr[j];
j--;
found=1;
}
if(found==1)
{
arr[j+1]=temp;
}//end of if
}//end of while loop
}//end of for loop

void printarray(int arr[], int n) /* function to print the array */
{
int i;
for(i=0;i<n;i++)
{
cout<<" "<<arr[i];
}
}

int main()
{
int arr[]={ 3,4,1,11,22,2,5,6};
int n=sizeof(arr)/sizeof(arr[0]);
cout<<"Before sorting array elements are: \n";
printarray(arr,n);
insertsort(arr,n);
cout<<"\nAfter sorting array elements are: \n";
printarray(arr,n);
}//end of main