#include<iostream>
using namespace std;

void Merge(int arry[], int left, int mid, int right)  //合并 
{
	int *temp = new int[right-left+1];  //中转数组
	int p = left;
	int q = mid + 1;
	int i = 0;       //记录temp数组的第一个空位置 
	while(p<=mid&&q<=right)  //对左右两部分按从小到大的顺序合并 
	{
		if(arry[p]<=arry[q])
		{
			temp[i] = arry[p];
			p++;
			i++;
		}
		else
		{
			temp[i] = arry[q];
			q++;
			i++;
		}
	} 
	
	while(p<=mid)  //若左部分有剩余，全部续到中转数组后 
	{
		temp[i] = arry[p];
		p++;
		i++;
	}
	
	while(q<=right) //若右部分有剩余，全部续到中转数组后
	{
		temp[i] = arry[q];
		q++;
		i++;
	}
	
	int j = 0;
	while(left<=right)  //将中转数组中的数据转移到原数组中 
	{
		arry[left] = temp[j];
		left++;
		j++;
	}
}

void MergeSort(int arry[], int left, int right)  //归并排序 
{
	if(left<right)
	{
		int mid = (left+right)/2;
		MergeSort(arry, left, mid); 
		MergeSort(arry, mid+1, right);
		Merge(arry, left, mid, right);
	}
}

int main()
{
	int a[] = {81,94,11,96,12,35,17,95,28,58,41,75,15};
	MergeSort(a,0,13);
	for(int i=0; i<13; ++i)
	{
		cout << a[i] << " ";
	}
}