mergesort.cpp

归并排序

#include "Mergesort.h"

template<class T>
void MergeSort(T a[],int left,int right) 
{
	if(left<right)
	{
		int i=(left+right)/2;
		T *b=new T[sizeof(a)];
		MergeSort(a,left,i);
		MergeSort(a,i+1,right);
		Merge(a,b,left,i,right);
		Copy(a,b,left,right);
	}
}

template<class T>
void Merge(T c[],T d[],int l,int m,int r)
{
	int i=l;
	int j=m+1;
	int k=l;
	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 q=i;q<=m;q++)
		d[k++]=c[q];
}

template<class T>
void Copy(T a[],T b[], int l,int r)
{
	for(int i=l;i<=r;i++)
		a[i]=b[i];
}