#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';
}