#include <iostream>
#include <algorithm>
#include <memory>
 
std::unique_ptr<int[]> insertionSort(const int original[], size_t size)
{
    int* result = new int[size];
    std::copy(original, original+size, result);
    for(int* p = result; p != result + size; ++p)
        std::rotate(std::upper_bound(result, p, *p), p, p+1);
    return std::unique_ptr<int[]>(result);
}
 
int main()
{
        int list[]={2,3,543,65,434,24,56,477,456,34,424,4546};
        auto sorted = insertionSort(list, 12);
 
        for (int i = 0; i < 12; i++)
            std::cout << list[i] << ' '; 
        std::cout << '\n';
        for (int i = 0; i < 12; i++)
            std::cout << sorted[i] << ' '; 
        std::cout << '\n';
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8bWVtb3J5PgoKc3RkOjp1bmlxdWVfcHRyPGludFtdPiBpbnNlcnRpb25Tb3J0KGNvbnN0IGludCBvcmlnaW5hbFtdLCBzaXplX3Qgc2l6ZSkKewogICAgaW50KiByZXN1bHQgPSBuZXcgaW50W3NpemVdOwogICAgc3RkOjpjb3B5KG9yaWdpbmFsLCBvcmlnaW5hbCtzaXplLCByZXN1bHQpOwogICAgZm9yKGludCogcCA9IHJlc3VsdDsgcCAhPSByZXN1bHQgKyBzaXplOyArK3ApCiAgICAgICAgc3RkOjpyb3RhdGUoc3RkOjp1cHBlcl9ib3VuZChyZXN1bHQsIHAsICpwKSwgcCwgcCsxKTsKICAgIHJldHVybiBzdGQ6OnVuaXF1ZV9wdHI8aW50W10+KHJlc3VsdCk7Cn0KCmludCBtYWluKCkKewogICAgICAgIGludCBsaXN0W109ezIsMyw1NDMsNjUsNDM0LDI0LDU2LDQ3Nyw0NTYsMzQsNDI0LDQ1NDZ9OwogICAgICAgIGF1dG8gc29ydGVkID0gaW5zZXJ0aW9uU29ydChsaXN0LCAxMik7CgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTI7IGkrKykKICAgICAgICAgICAgc3RkOjpjb3V0IDw8IGxpc3RbaV0gPDwgJyAnOyAKICAgICAgICBzdGQ6OmNvdXQgPDwgJ1xuJzsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDEyOyBpKyspCiAgICAgICAgICAgIHN0ZDo6Y291dCA8PCBzb3J0ZWRbaV0gPDwgJyAnOyAKICAgICAgICBzdGQ6OmNvdXQgPDwgJ1xuJzsKfQo=