#include<stdio.h>
#include<stdlib.h>

int N=3;
typedef struct{
	 int id;
	 int key;
	 }tnode;

void merge(tnode *r,int low,int m,int high);
void mergesortdc(tnode *r,int low,int high);
void outlist(tnode *r);

main(){ 
	int i;
	tnode *r;
	printf("輸入所要排序的元素的數目N=");
	scanf("%d",&N);
	r=new tnode[N+1];
	printf("input key:");
	for(i=1;i<=N;i++)
		scanf("%d",&r[i].key);
	mergesortdc(r,1,N);
	outlist(r);
   	delete[]r;
}
void merge(tnode *r,int low,int m,int high){ 
	int i=low,j=m+1,p=0;
	tnode *r1;
	r1=(tnode*)malloc((high-low+1)*sizeof(tnode));
	if(!r1){ 
		printf("insuficient memoryavailable!");
		return;
	}
	while(i<=m && j<=high)
		r1[p++]=(r[i].key<=r[j].key)? r[i++]: r[j++];
	while(i<=m)
		r1[p++]=r[i++];
	while(j<=high)
		r1[p++]=r[j++];
	for(p=0,i=low;i<=high;p++,i++)
		r[i]=r1[p];
}
void mergesortdc(tnode *r,int low,int high){
	int mid;
	if(low<high){
		mid=(low+high)/2;
		mergesortdc(r,low,mid);
		mergesortdc(r,mid+1,high);
		merge(r,low,mid,high);
	}
}
void outlist(tnode *r){ 
	int i;
	printf("排序后：\n");
	for(i=1;i<=N;i++)
		printf("%d ",r[i].key);
	printf("\n");
}