#include <iostream>

template <typename T>
T* merge(T* left, T* right, unsigned lsize, unsigned rsize) {
	unsigned size = lsize + rsize;
	T* merged = new T[size];
	for (int i = 0; i < size; i++) {
		if (rsize == 0 || (lsize != 0 && *left < *right)) { 
			merged[i] = *(left++);
			lsize--;
		}
		else { 
			merged[i] = *(right++);
			rsize--;
		}
	}
	return merged;
}

template <typename T>
T* mergeSort(T* arr, unsigned size) {
	if (size == 1) return arr;

	unsigned leftSize = size / 2, rightSize = size - leftSize;
	return merge(mergeSort(arr, leftSize), mergeSort(arr + leftSize, rightSize), leftSize, rightSize);
}