Translate the insertion sort algorithm to C++

[Maria Ramos]

Solved!
Thank You ~^^~

[toum]

You're missing a inner = inner - 1; in the while loop.

[Maria Ramos]

so I return the copy already?

[Cubbi]

That task is formulated using very unconventional, for C++, concepts.

Here's a try to make it make some sense:

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

demo: http://ideone.com/RmdCdH

but seriously, a C++ sort function would take an iterator range, not pointer+size, and if it has to create a new range, it would take an output iterator.