#include<iostream>
#include<cmath>
using namespace std;
//a原数组 s起始 m中间 e终点 tmp临时数组 
void merge(int a[], int s, int m, int e, int tmp[]){ //归并时间复杂度O(n) 
	int k=0;
	int i=s,j=m+1;
	while(i<=m && j<=e){
		if(a[i] < a[j])
			tmp[k++]=a[i++];
		else
			tmp[k++]=a[j++];
	}
	while(i<=m){
		tmp[k++]=a[i++];
	}
	while(j<=e){
		tmp[k++]=a[j++];
	}
	for(int u=0;u<k;u++){
		a[s+u]=tmp[u];
	}
}

void mergesort(int a[], int s, int e, int tmp[]){ //分治 
	if(s<e){
		int m=s+(e-s)/2;
		mergesort(a,s,m,tmp);
		mergesort(a,m+1,e,tmp);
		merge(a,s,m,e,tmp);
	}
}
int main(){
	int a[10]={13,27,19,2,8,12,2,8,30,89}; 
	int tmp[10];
	int size=sizeof(a)/sizeof(int);
	mergesort(a,0,size-1,tmp);
	
	for(int i=0;i<size;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	return 0;
}