#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>
#include <Windows.h>

using namespace std;

void mergeSort(vector<int>&, int, int, vector<int> &temp);
void merge(vector<int>&, int, int, int, vector<int> &temp);

void mergeSort(vector<int> &a, int l, int r, vector<int> &temp)
{
	if (r > l){  //если больше 1 элемента
		int mid = (r + l) / 2; //выбираем середину

		mergeSort(a, l, mid, temp);  //разделяем левую половину
		temp.resize(0);
		mergeSort(a, mid + 1, r, temp); //разделяем правую половину
		temp.resize(0);
		merge(a, l, mid, r, temp); //сливаем левую и праву половину
	}
}

void merge(vector<int> &a, int l, int mid, int r, vector<int> &temp)
{
	//vector<int> temp; //вспомогательный массив

	int i = l;
	int j = mid + 1;

	while(i <= mid && j <= r){  //пока обе половины не пустые
		if (a[i] <= a[j]){		//если элемент их левой половины меньше
			temp.push_back(a[i]); //то записываем его
			i++;
		}else{
			temp.push_back(a[j]); //иначе берём элемент из правой половины
			j++;
		}
	}

	while(i <= mid){ //если еще есть элементы в левой части, то дописываем их
		temp.push_back(a[i]);
		i++;
	}

	while(j <= r){
		temp.push_back(a[j]); //если еще есть элементы в правой части, то дописываем их
		j++;
	}

	i = 0;

	while(l <= r){ //переписываем элементы из вспомогательного массива в основной
		a[l] = temp[i];
		l++;
		i++;
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

	srand(time(NULL));

	int n;

	n = 15000;

	vector<int> a(n);

	for (int i = 0; i < n; i++) // считываем изначальный массив
	{
		a[i] = rand() % 1000000;
	}

	auto ti1 = GetTickCount();
	vector<int> temp;

	mergeSort(a, 0, a.size() - 1, temp); //выполняем сортировку

	auto ti2 = GetTickCount();

	cout << (double)(ti2 - ti1) << " milliseconds" << endl;

	for (int i = 0; i < n; i++) // выводим отсортированный массив
	{
		cout << a[i] << " ";
	}

}