implementing merge sort in C

Question

I've studied the theory of the merge sort, but I'm not sure how to implement it in C++. My question is if merge sort generates arrays recursively. But how can we construct arrays in runtime while implementing? Alternatively, what is the usual approach to this?

Answer 1

To respond to the question: 

std::vectorT> is used to create dynamically sized arrays at runtime. 

Ideally, you'd use one of these to get feedback. 

If not, they are simple to convert. 

For instance, you might make two arrays like this:

template <typename T>
void merge_sort(std::vector<T>& array) {
    if (1 < array.size()) {
        std::vector<T> array1(array.begin(), array.begin() + array.size() / 2);
        merge_sort(array1);
        std::vector<T> array2(array.begin() + array.size() / 2, array.end());
        merge_sort(array2);
        merge(array, array1, array2);
    }
}

However, allocating dynamic arrays is relatively slow and generally should be avoided when possible. For merge sort you can just sort subsequences of the original array and in-place merge them. It seems, std::inplace_merge() asks for bidirectional iterators.