合并排序／归并排序（递归与分治）－算法设计与分析

const int maxn=100;

int a[maxn];

void Merge_Array(int l,int r)

{

    int m=(l+r)>>1;

    int i=l,j=m+1,n=r;

    int k=0;

    int tmp[maxn];

    while(i<=m && j<=n)

    {

        if(a[i]<a[j])tmp[k++]=a[i++];

        else tmp[k++]=a[j++];

    }

    while(i<=m)tmp[k++]=a[i++];

    while(j<=n)tmp[k++]=a[j++];

    for(int i=0;i<k;i++)

        a[l+i]=tmp[i];

}

void Merge_sort(int l,int r)

{

    int mid=(l+r)>>1;

    if(l<r)

    {

        Merge_sort(l,mid);

        Merge_sort(mid+1,r);

        Merge_Array(l,r);

    }

}

int main()

{

    int n;

    cin>>n;

    for(int i=0;i<n;i++)cin>>a[i];

    Merge_sort(0,n-1);

    for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl;

    return 0;

}