#include <iostream>
using namespace std;
#define NUM 10
template <class T>
class List
{
public:
	List(int MaxListSize=10);
	~List(){};
	void Copy(T a[],T b[]);
	void Merge(T c[],T d[],int l,int m,int r);
	void MergeSort(T a[],int left,int right);
	
private:
	int MaxSize;
};

template<class T>
List<T>::List(int MaxListSize)
{
	MaxSize=MaxListSize;
	
}

template<class T>
void List<T>::Copy(T a[],T b[])
{
	for(int z=0;z<NUM;z++)
		b[z]=a[z];
	for(int n=0;n<NUM;n++)
		cout<<a[n]<<" ";
	cout<<endl;
}

template<class T>
void List<T>::Merge(T c[],T d[],int l,int m,int r)
{
	int i=l;          //第一段的游標
	int j=m+1;        //第二段的游標
	int k=l;          //結(jié)果的游標
	while((i<=m)&&(j<=r))
	{
		if(c[i]<=c[j])
			d[k++]=c[i++];
		else
			d[k++]=c[j++];
	}
		if(i>m)
		{
			for(int q=j;q<=r;q++)
				d[k++]=c[q];
		}
		else
		{
			for(int p=i;p<=m;p++)
				d[k++]=c[p];
		}
}


			

template<class T>
void List<T>::MergeSort(T a[],int left,int right)   //對a[left:right]中的元素進行排序
{
	T b[NUM];
	for(int c=0;c<NUM;c++)
		b[c]=a[c];
	if(left<right)
	{
		int i=(left+right)/2;
		MergeSort(a,left,i);
		MergeSort(a,i+1,right);
		Merge(a,b,left,i,right);
		Copy(b,a);
		
	}
}