Acwing 787. Merge sort

787. Merge sort

subject ：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int N=1e5+10;

int n,a[N],m;

void sort1(){
    
    sort(a,a+n);
}
void sort2(int l,int r){
    
    if(l>=r) return;
    int mid=(l+r)>>1;
    //cout<<mid<<endl;
    sort2(l,mid);
    sort2(mid+1,r);
    int t[N],k=0;
    int  i=l,j=mid+1;
    for(;i<=mid && j<=r;){
    
        if(a[i]<=a[j]) t[k++]=a[i++];
        else t[k++]=a[j++];
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(int i=0;i<k;i++){
    
        a[l+i]=t[i];
    }

}

void sort3(int l,int r){
    
    if(l>=r) return ;
    int i=l-1,j=r+1,x=(l+r)>>1;
    while(i<j){
    
        do i++;while(a[i]<a[x]);
        do j--;while(a[j]>a[x]);
        if(i<j) swap(a[i],a[j]);
    }
    sort3(l,i);sort3(i+1,r);
}
int main(){
    
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    //sort1();
    sort2(0,n-1);
    //sort3(0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}