归并排序

归并排序

　时间复杂度 O(nlogn)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;

const int MAX_A = 100009;
//合并
void Merge(int (&c)[MAX_A],int l,int m,int r)
{
    int mp[r-l+2];
    int i=l,j=m+1,k=0;
    while(i<=m&&j<=r) 
    {
        if(c[i]<=c[j])
            mp[k++]=c[i++];
        else
            mp[k++]=c[j++];
    }
    //合并未查到的左或右区间
    while(i<=m) mp[k++]=c[i++];
    while(j<=r) mp[k++]=c[j++];
    //赋值给原数组
    for(int i=0;i<k;i++) c[i+l]=mp[i];
}

void Merge_sort(int (&b)[MAX_A],int l,int r)
{
    if(l < r)
    {  //递归二分
        int m=(l+r)/2;
        Merge_sort(b,l,m);
        Merge_sort(b,m+1,r);
        Merge(b,l,m,r);
    }
}
int main()
{
   int a[MAX_A],n;
   while(~scanf("%d",&n))
   {
       for(int i=0;i<n;i++)
           scanf("%d",&a[i]);
    
        int l=0,r=n-1;
        Merge_sort(a,l,r);
        
        for(int i=0;i<n;i++)
            printf("%d ",a[i]);
        printf("
");
   }
}