To answer the question: Creating dynamically sized arrays at run-time is done using std::vector<T>. Ideally, you'd get your input using one of these. If not, it is easy to convert them. For example, you could create 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.