#include<iostream>
using namespace std;
int t[9];
int ta; //线性扫描得到的标记数
void Merge(int c[],int d[],int l,int m,int r);
void MergePass(int x[],int y[],int s,int n) ;
//先声明函数
void MergeSort(int a[],int n)
{
int *b=new int[n];
int s=1;
while(s<ta)
{
MergePass(a,b,s,n); //合并到数组b
s+=s; //两个数组合并后规模翻倍
MergePass(b,a,s,n); //合并到数组a ,并且保证a中的数组元素已经排好序
s+=s;
}
}
void MergePass(int x[],int y[],int s,int n)
{
int i=0;
while(i<=ta-2*s)
{ //合并大小为s的相邻2段子数组
int r=((i+2*s)<ta)?t[i+2*s]:n;
Merge(x,y,t[i],t[i+s]-1,r-1);
i=i+2*s;
}
if(i+s<ta) //剩下元素少于2s,即s~2s
Merge(x,y,t[i],t[i+s]-1,n-1);
else if(i<ta)
{
for(int j=t[i];j<=n-1;j++)
y[j]=x[j];
}
}
void Merge(int c[],int d[],int l,int m,int r)
{//合并c[l:m]和c[m+1:r]到d[l:r]
int i=l,j=m+1,k=r;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
d[l++]=c[i++]; //d[l]=c[i],l++,i++
else
d[l++]=c[j++];
}
if(i>m)
for(int q=j;q<=r;q++) //说明i全部复制到d了,只需把剩下的j复制到d中,且此时c中元素是有序的,可以直接复制
d[l++]=c[q];
else
for(int p=i;p<=m;p++) //说明j全部复制到d了,只需把剩下的i复制到d中,且此时c中元素是有序的,可以直接复制
d[l++]=c[p];
}
void PrintArray(int a[],int n)
{ //输出数组中的元素
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void GetBPoint(int a[],int b[],int n,int &m)
{ //自然合并排序线性扫描得到的标记数
int j=0;
b[j++]=0;
for(int i=0;i<n-1;i++)
{
if(a[i+1]<a[i])
b[j++]=i+1; //记录端点
}
m=j; //记录端点个数
}
int main()
{
int a[]={4,9,2,6,1,5,7,3};
cout<<"原数组:";
PrintArray(a,8);
GetBPoint(a,t,8,ta);
MergeSort(a,8);
cout<<"排序后:";
PrintArray(a,8);
return 0;
}