#include<iostream>
 
using namespace std;
 
void insertion_sort(int n, int arr[])
{
   cout<<"insertion sort"<<endl;
 
   for(int j=1;j<n;j++)
   {
      int key=arr[j];
      int i=j-1;
      while(i>=0 && arr[i]>key)
      {
         arr[i+1]=arr[i];
         i--;
      }
      arr[i+1]=key;
   }
}
 
int main()
{
   int n=5;
   int arr[5]={5,3,6,7,1};
 
   insertion_sort(n,arr);
 
   for(int i=0;i<n;i++)
   {
      cout<<arr[i]<<" ";
 
   }
}
 

I2luY2x1ZGU8aW9zdHJlYW0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBpbnNlcnRpb25fc29ydChpbnQgbiwgaW50IGFycltdKQp7CiAgIGNvdXQ8PCJpbnNlcnRpb24gc29ydCI8PGVuZGw7CgogICBmb3IoaW50IGo9MTtqPG47aisrKQogICB7CiAgICAgIGludCBrZXk9YXJyW2pdOwogICAgICBpbnQgaT1qLTE7CiAgICAgIHdoaWxlKGk+PTAgJiYgYXJyW2ldPmtleSkKICAgICAgewogICAgICAgICBhcnJbaSsxXT1hcnJbaV07CiAgICAgICAgIGktLTsKICAgICAgfQogICAgICBhcnJbaSsxXT1rZXk7CiAgIH0KfQoKaW50IG1haW4oKQp7CiAgIGludCBuPTU7CiAgIGludCBhcnJbNV09ezUsMyw2LDcsMX07CgogICBpbnNlcnRpb25fc29ydChuLGFycik7CgogICBmb3IoaW50IGk9MDtpPG47aSsrKQogICB7CiAgICAgIGNvdXQ8PGFycltpXTw8IiAiOwoKICAgfQp9Cg==