基本思想

分而治之

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log₂n。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

代码实现

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 int a[500005],b[500005];//b 为排完序的数组  6 long long ans; 7 void mergesort(int l,int r) 8 { 9     if(l==r)10     return;11     int mid=(l+r)>>1;12     mergesort(l,mid);13     mergesort(mid+1,r);14     int i=l,j=mid+1,k=l;15     while(i<=mid&&j<=r)16     {17         if(a[i]<=a[j])18         b[k++]=a[i++];19         else b[k++]=a[j++];20     }21     while(i<=mid) b[k++]=a[i++];22     while(j<=r) b[k++]=a[j++];23     for(int q=l;q<=r;q++) a[q]=b[q];24 }25 int main()26 {27     int n;28     scanf("%d",&n);29     for(int i=1;i<=n;i++)30         scanf("%d",&a[i]);31     mergesort(1,n);32     for(int i=1;i<=n;i++)33     printf("%d ",b[i]);34     return 0;35 }