归并排序

归并排序

//使用分治的思想，将所有的过程都分解成两个，在结束排序之后，我们返回，然后就可以进行排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int s[N];
void merge_sort(int l,int r)
{
    if(l>=r)return ;
    int mid = (l + r)>>1;

    merge_sort(l,mid),merge_sort(mid+1,r);

    int i=l,j=mid+1,t=1,k[r-l+1];
    while(i<=mid&&j<=r)
    {
        if(s[i]<=s[j])k[t++]=s[i++];
        else k[t++]=s[j++];
    } 
    while(i<=mid)k[t++]=s[i++];
    while(j<=r)k[t++]=s[j++];
    for(int t=1,i=l;i<=r;i++,t++)s[i]=k[t];
}
int main()
{   
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&s[i]);

    merge_sort(1,n);

    for(int i=1;i<=n;i++)printf("%d ",s[i]);

    return 0;
}