#include<iostream>
#include<vector>
#include<algorithm>
 
void insertionSort(std::vector<int>& vec){
 for(auto it = vec.begin(); it != vec.end(); it++)
 {
   // Search
   auto const insertion_point = std::upper_bound(vec.begin(), it, *it);
 
   //insert
   std::rotate(insertion_point, it, it+1);
 }
}
 
void print(std::vector<int> const& vec){
 for( int x : vec)
  std::cout << x << " ";
std::cout << '\n';
}
 
int main(){
 std::vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};
 insertionSort(arr);
 print(arr);
}
 

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8YWxnb3JpdGhtPgoKdm9pZCBpbnNlcnRpb25Tb3J0KHN0ZDo6dmVjdG9yPGludD4mIHZlYyl7CiBmb3IoYXV0byBpdCA9IHZlYy5iZWdpbigpOyBpdCAhPSB2ZWMuZW5kKCk7IGl0KyspCiB7CiAgIC8vIFNlYXJjaAogICBhdXRvIGNvbnN0IGluc2VydGlvbl9wb2ludCA9IHN0ZDo6dXBwZXJfYm91bmQodmVjLmJlZ2luKCksIGl0LCAqaXQpOwoKICAgLy9pbnNlcnQKICAgc3RkOjpyb3RhdGUoaW5zZXJ0aW9uX3BvaW50LCBpdCwgaXQrMSk7CiB9Cn0KCnZvaWQgcHJpbnQoc3RkOjp2ZWN0b3I8aW50PiBjb25zdCYgdmVjKXsKIGZvciggaW50IHggOiB2ZWMpCiAgc3RkOjpjb3V0IDw8IHggPDwgIiAiOwpzdGQ6OmNvdXQgPDwgJ1xuJzsKfQoKaW50IG1haW4oKXsKIHN0ZDo6dmVjdG9yPGludD4gYXJyID0gezIsIDEsIDUsIDMsIDcsIDUsIDQsIDZ9OwogaW5zZXJ0aW9uU29ydChhcnIpOwogcHJpbnQoYXJyKTsKfQo=