#include<iostream>
#include<vector>
 
void insertionSort(std::vector<int>& vec)
{
for(unsigned j = 1; j < vec.size(); j++)
 {
  int key = vec[j];
  int i = j-1;
 
  while(i >= 0 && vec[i] > key)
  {
    vec[i+1] = vec[i];
    i--;
  }
  vec[i+1] = key;
 }
}
 
void print(std::vector<int> vec){
 for(unsigned i = 0; i < vec.size(); i++){
  std::cout << vec[i] << " ";
  }
}
 
int main(){
std::vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};
insertionSort(arr);
print(arr);
std::cout<<std::endl;
}
 

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KCnZvaWQgaW5zZXJ0aW9uU29ydChzdGQ6OnZlY3RvcjxpbnQ+JiB2ZWMpCnsKZm9yKHVuc2lnbmVkIGogPSAxOyBqIDwgdmVjLnNpemUoKTsgaisrKQogewogIGludCBrZXkgPSB2ZWNbal07CiAgaW50IGkgPSBqLTE7CgogIHdoaWxlKGkgPj0gMCAmJiB2ZWNbaV0gPiBrZXkpCiAgewogICAgdmVjW2krMV0gPSB2ZWNbaV07CiAgICBpLS07CiAgfQogIHZlY1tpKzFdID0ga2V5OwogfQp9Cgp2b2lkIHByaW50KHN0ZDo6dmVjdG9yPGludD4gdmVjKXsKIGZvcih1bnNpZ25lZCBpID0gMDsgaSA8IHZlYy5zaXplKCk7IGkrKyl7CiAgc3RkOjpjb3V0IDw8IHZlY1tpXSA8PCAiICI7CiAgfQp9CgppbnQgbWFpbigpewpzdGQ6OnZlY3RvcjxpbnQ+IGFyciA9IHsyLCAxLCA1LCAzLCA3LCA1LCA0LCA2fTsKaW5zZXJ0aW9uU29ydChhcnIpOwpwcmludChhcnIpOwpzdGQ6OmNvdXQ8PHN0ZDo6ZW5kbDsKfQo=