合并排序算法

#include<iostream.h>
intn;

//将两个已经排好序的子序列A[P..Q]和A[P+1..R]合并成一个已排好序的子序列A[P..R]
voidmerge(intA[],intp,intq,intr)
{
inti,j,t;
int*temp=newint[n];//用来暂存合并后的序列

t=p;//序列temp的下标计数器,从p开始
i=p;//左子序A[P..Q]的下标计数器,从p开始
j=q+1;//右子序A[Q+1..R]的下表计数器,从q+1开始
//合并序列
while(t<=r)
if(i<=q&&(j>r||A[i]<=A[j]))
temp[t++]=A[i++];
else
temp[t++]=A[j++];
//将temp中的序列赋值给A
for(i=p;i<=r;i++)
A[i]=temp[i];
delete[]temp;
}
//合并排序过程
voidmergeSort(intA[],intp,intr)
{
intq;
if(p!=r)//若子序列A中不止一个元素
{
q=(int)((p+r-1)/2);//计算中间下标,将子序列A分为左子序列和右子序列
mergeSort(A,p,q);//对左子序列进行合并排序
mergeSort(A,q+1,r);//对右子序列进行合并排序
merge(A,p,q,r);//对左子序类和右子序列进行合并
}
}
//主程序
intmain()
{
while(cin>>n)
{
inti,*A=newint[n];
for(i=0;i<n;i++)
cin>>A[i];
mergeSort(A,0,n-1);
for(i=0;i<n;i++)
i==n-1?cout<<A[i]<<endl:cout<<A[i]<<"";
delete[]A;
}
return0;
}