自底向上的归并排序
void Mergesort(int a[],int n)
{
int len;
for(len=1;len<n;len=2*len)
{
MergePass(a,len,n);//从步长为1开始归并
}
}
void MergePass(int a[],int len,int n)//归并
{
int i;
for(i=0;i+2*len<=n;i+2*len)
{
Merge(a,i,i+len-1,i+2*len-1);//归并
}
if(i+len<=n)//归并
Merge(a,i,i+len-1,n-1);
}
void Merge(int a[],low,mid,high)//两个有序的序列合并在一起
{
int *temp;
int i=low;
int j=mid+1;
int k=0;
tmp=(int *)malloc((high-low+1)*sizeof(int));
while(i<=mid&&j<=high)
{
if(a[i]<=a[j])
{
tmp[k++]=a[i++];
}
else
{
tmp[k++]=a[j++];
}
}
while(i<=mid)
{
tmp[k++]=a[i++];
}
while(j<=high)
{
tmp[k++]=a[j++];
}
for(k=0,i<low;i<=high;k++,i++)
{
a[i]=tmp[k];
}
free(tmp);
}