归并排序

luckydrawbox · 2021-08-28 23:36:48 · 个人记录

对一个下标在 [l,r] 间的数组 a 排序。

一般可以这么调用：gsort(a,1,n)，把 a_{1\sim n} 排好序。

int r[N];
void gsort(int *a,int x,int y){
    if(x==y)
        return;
    int mid=(x+y)>>1;
    gsort(a,x,mid);
    gsort(a,mid+1,y);
    int i=x,j=mid+1,k=x;
    while(i<=mid&&j<=y)
        if(a[i]<=a[j])
            r[k++]=a[i++];
        else
            r[k++]=a[j++];
    while(i<=mid)
        r[k++]=a[i++];
    while(j<=y)
        r[k++]=a[j++];
    for(int i=x;i<=y;i++)
        a[i]=r[i];
}

时间复杂度 O(n\log n)，空间复杂度 O(n)。