mergesort.cpp

来自「常用算法与数据结构原代码」· C++ 代码 · 共 55 行

template <class T>
void Merge_Step(T e[],T a[],int s,int m,int n)
{
	int i,j,k;
	k=i=s;
	j=m+1;
	while (i<=m && j<=n)
		if (e[i]<=e[j])
			a[k++]=e[i++];
		else 
			a[k++]=e[j++];
	while (i<=m)
		a[k++]=e[i++];
	while (j<=n)
		a[k++]=e[j++];
}

template <class T>
void Merge_Pass(T e[],T a[],int n,int len)
{
	int f_s,s_end;
	f_s=0;
	while (f_s+len<n)
	{
		s_end=f_s+2*len-1;
		if (s_end>=n)
			s_end=n-1;
		Merge_Step(e,a,f_s,f_s+len-1,s_end);
		f_s=s_end+1;
	}
	if (f_s<n)
		for (;f_s<n;f_s++)
			a[f_s]=e[f_s];
}

template <class T>
void MergeSort(T e[],int n)
{
	int *p;
	p=new int[n];
	int len=1,f=0;
	while (len<n)
	{
		if (f==0)
			Merge_Pass(e,p,n,len);
		else
			Merge_Pass(p,e,n,len);
		len*=2;
		f=1-f;
	}
	if (f)
		for (f=0;f<n;f++)
			e[f]=p[f];
	delete []p;
}