#include <iostream>
#include <iomanip>
using namespace std;

template<class T>
void Merge(const T *iniList, T *mergedList,const int l, const int m, const int n) {
	int pos1 = l, posf = l, pos2 = m+1;
	
	for (;pos1<=m&&pos2<=n;posf++) {
		if (iniList[pos1] < iniList[pos2]) {
			mergedList[posf] = iniList[pos1];
			pos1++;
		}
		else {
			mergedList[posf] = iniList[pos2];
			pos2++;
		}
	}

	
	if (pos1 <= m) 
		for (; pos1 <= m; pos1++,posf++) 
			mergedList[posf] = iniList[pos1];
		

	if (pos2 <= n) 
		for (; pos2 <= n; pos2++, posf++) 
			mergedList[posf] = iniList[pos2];
		
}
template<class T>
T* MergeSort(T *iniList, const int n) {
	T *tempList = new T[n];
	for (int s = 1; s < n; s = s * 2) {
		int i = 0;
		for (; i < n - 2*s + 1; i = i + 2*s)
			Merge<T>(iniList, tempList, i, i + s - 1, i + 2*s - 1);
		
		iniList = tempList;
		
		for (int j = 0; j < n; j++)
			cout << iniList[j] << ',';
		cout << endl;
		system("PAUSE");

		if ((i + s - 1) < n) Merge<T>(iniList, tempList, i, i + s - 1, n);
		else {
			for (; i < n; i++)
				tempList[i] = iniList[i];
		}
	}
	return tempList;
}
// main function
int main(){
	int a[10] = { 26,5,77,1,61,11,59,15,48,19};
	int *n= MergeSort<int>(a, 10);
	system("PAUSE");
}