思路

• 类似于二分的操作，把每一段空间分成两半，直到空间长度等于一（递归实现）
• 合并过程，则对两个区间分别分配一个pointer，比较两个pointer指向的元素，然后存入数组
• 对于每一个片段需要的合并，一共有的层次，所以复杂度为

实现代码

#include<bits/stdc++.h>
using namespace std;
int a[505050],b[505050];
long long ans=0;
void merge(int l,int r,int mid){
    int p1=l,p2=mid+1;
    for(int i=l;i<=r;i++){
        if((p2>r)||(p1<=mid&&a[p1]<=a[p2])){
          //注意比较的时候是否取等,意思是同样大小的时候是先存位置靠前的还是先存位置靠后的
            b[i]=a[p1++];
        }else{
            b[i]=a[p2++];
        }
    }
    for(int i=l;i<=r;i++)a[i]=b[i];
}
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);
    merge(l,r,mid);
    return;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    merge_sort(1,n);
	for(int i=1;i<=n;i++)printf("%d",a[i]);
    return 0;
}

意义

• 处理逆序对问题，通过归并排序可以在排序的过程中顺带计算序列中的逆序对个数

  [逆序对模板题]

• ……