#include <iostream.h>
#include <stdio.h>
//#define OK 1
//#define ERROR 0
#define MAXSIZE 100
typedef int KeyType;
//typedef char InfoType;

typedef struct{
	KeyType key;
}redtype;
typedef struct{
	redtype r[MAXSIZE+1];
	int length;
}SqList;

void BubbleSort(SqList &L)
{
	int i=L.length,j,l;
	KeyType x;
	while(i>1)
	{
		l=1;
		for(j=1;j<i;j++)
			if(L.r[j+1].key<L.r[j].key)
			{
				x=L.r[j+1].key;
				L.r[j+1].key=L.r[j].key;
				L.r[j].key=x;
				l=j;
			}
	i=l;
	}
}

void insertsort(SqList &L)
{
	for(int i=2;i<=L.length;++i)
	{
		if(L.r[i].key<L.r[i-1].key)
		{
		L.r[0]=L.r[i];
		L.r[i]=L.r[i-1];
		for(int j=i-2;L.r[0].key<L.r[j].key;--j)
		
			L.r[j+1]=L.r[j];
			L.r[j+1]=L.r[0];
		
		}
	}
}
void merge( redtype SR[],redtype TR[],int i,int m,int n){int j,int k;
for(j=m+1,k=i;i<=m&&j<=n;++k)
{if (SR[i].key<=SR[j].key)TR[k]=SR[i++];
else TR[k]=SR[j++];
}
while(i<=m)TR[k++]=SR[i++];
while(j<=n)TR[k++]=SR[j++];
}//Merge

void msort(redtype SR[],redtype TR1[],int s,int t)
{int m;redtype TR2[MAXSIZE+1];
if(s==t)TR1[s]=SR[s];
else{
	m=(s+t)/2;msort(SR,TR2,s,m);msort(SR,TR2,m+1,t);merge(TR2,TR1,s,m,t);}}

void Display(SqList &L)
{
	int i;
	for(i=1;i<=L.length;i++)
		cout<<L.r[i].key<<' ';
	cout<<endl;
}

void main(){

	int h;



	cout<<"        1->insert "<<endl;
	cout<<"        2->BubbleSort "<<endl;
	cout<<"        3->merge "<<endl;
	cin>>h;
    if(h==1 || h==2 || h==3 || h==0)
	{
	while(h!=0)
	{

	SqList L;
	int n,i;
	cout<<"請輸入要排序的數的個數:"<<endl;
	cin>>n;
	cout<<"請輸入要排序的數:"<<endl;
	for(i=1;i<=n;i++)
		cin>>L.r[i].key;
	L.length=n;
	cout<<"排序前:"<<endl;
	Display(L);

    if(h==1)
	{
	    insertsort(L);
	}
    if(h==2)
	{
       BubbleSort(L);
	}
	if(h==3)
	{
		msort(L.r,L.r,1,L.length);

	}

	cout<<"排序后:"<<endl;
	Display(L);
	}
   }
	else
	{
		cout<<"inser error"<<endl;
	}
}