给大家分享一下归并排序的思路。

思路

归并排序是什么？分裂+合并。

首先把数组 $a$ 平分成两半。

如可以把 $(3,2,1,7,5,6,4,8)$ 分成 $(3,2,1,7)$ 和 $(5,6,4,8)$。

然后把 $(3,2,1,7)$ 分成 $(3,2)$ 和 $(1,7)$。

接着把 $(3,2)$ 分成 $(3)$ 和 $(2)$。

显然不能继续分下去，那就合并。

首先把首元素更小的 $(2)$ 的数组的首元素提取出来，变成空数组后，也只能把 $(3)$ 加入。得到了 $(2,3)$。

然后以此类推，$(3,2,1,7)$ 变成了 $(1,2,3,7)$；$(5,6,4,8)$ 变成了 $(4,5,6,8)$，最后合并这两个子数组，首元素比较，合并顺序为 $\text {lllrrrlr}$（$l$ 表示提取 $(1,2,3,7)$，$r$ 表示提取 $(4,5,6,8)$）。

显然，归并排序运用了递归和分治的思想。

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[100005],w[100005];
void merge(int l,int r){
    if (l==r)
        return ;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1,cnt=l;
    while (i<=mid&&j<=r)
        if (a[i]<=a[j])
            w[cnt++]=a[i++];
        else
            w[cnt++]=a[j++];
    while (i<=mid)
        w[cnt++]=a[i++];
    while (j<=r)
        w[cnt++]=a[j++];
    for (int k=l;k<=r;k++)
        a[k]=w[k];
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    merge(1,n);
    for (int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}