# include "iostream.h"
# include "time.h"
# include "stdlib.h"

void merge(int *p,int low,int mid,int high)
{
	int *q;
	int x=high-low+1;
	q=new int[x];

	int s=low;
	int	t=mid+1;
	int	k=0;
	while(s<=mid && t<=high)
	{
		if(p[s-1]<=p[t-1])
		{
			q[k]=p[s-1];
			s++;
		}
		else
		{
			q[k]=p[t-1];
			t++;
		}
		k++;
	}
	if(s==(mid+1))
	{
		for(;k<x&&t<=high;k++)
		{
			q[k]=p[t-1];
			t++;
		}
	}
	else
	{
		for(;k<x&&s<=high;k++)
		{
			q[k]=p[s-1];
			s++;
		}
	}

	
	for(k=0;low<=high;low++,k++)
	{
		p[low-1]=q[k];
	}
	delete []q;
}

void mergesort(int *a,int low,int high)
{
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		mergesort(a,low,mid);
		mergesort(a,mid+1,high);
		merge(a,low,mid,high);
	}
}

void main()
{
	int *m;
	int i;
	int num;
	int chose;
	char ch='y';

	cout<<"       合并排序!      "<<endl;
    
	while(ch=='y'||ch=='Y')
	{
		cout<<"請輸入您想隨機生成的數組的長度:";
		cin>>num;
	
		m=new int[num];

		cout<<"請選擇數組的生成方式："<<endl;
		cout<<"1.隨機生成"<<endl;
		cout<<"2.手動輸入"<<endl;
		cin>>chose;
		if(chose==1)
		{
			cout<<"隨機生成數組：" << endl;
			srand((unsigned)time(NULL));                
			for(i=0;i<num;i++)
			{
				m[i] = rand() % 100;
				cout<<" "<<m[i]<<" " << endl;
			}
		}	
		else if(chose==2)
		{
			cout<<"請輸入并以空格隔開：";
			for(i=0;i<num;i++)
			{
				cin >> m[i];
			}
		}
		
		mergesort(m,1,num);

		cout<<"排序后的數組為："<<endl;
		for(i=0;i<num;i++)
		{
			cout<<" "<<m[i]<<" " << endl;
		}
		delete []m;
		cin.ignore();
		cout<<endl<<"是否繼續(y/n)："<<endl;
		cin.get(ch);
	}
}