 ### C++ program for insertion sort algorithm

Description:
insertion sort algorithm is simple sorting algorithm. it is less efficient for large number of data compare to heap sort, quick sort, merge sort.
this algorithm picks one elements at a time and insert the element at location belongs to sorted list and repeats until no input elements remain unsorted.
Time complexity is O(n*2) in average case and worst case and O(n) in best case(All elements are already sorted).

LOGIC:
LOOP from i = second element of list to last element
pick element array[i] and insert it into sorted list array[0...i-1].

C++ code:

```#include<iostream>
using namespace std;
void insertion_sort(int[], int);
void print_list(int[], int);
void insertion_sort(int arr[], int n)
{
int i,j,key;
for(i=1;i<n;i++)
{
key=arr[i];
for(j=i-1;j>=0 && key<arr[j];j--)
arr [j + 1 ] = arr [j];
arr[j+1]=key;
}
}
void print_list(int arr[], int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
}
int main()
{
int arr[]={25,15,12,45,6,35,26,13};
insertion_sort(arr,8);
print_list(arr,8);
return 0;
}```

`input: 25,15,12,45,6,35,26,13`
`Output: 6 12 13 15 25 26 35 45` 