归并排序，简而言之就是将两个内部顺序已经确定的集合进行合并，使得合并后的集合仍然有序

那么对于一个无序集合，就需将其递归到最底层从底开始回归上一层，这样不停地将每个集合内部归并而有序。

 

那么对于一个集合的逆序对该如何求呢？

比如集合{5,4,3,2,1}逆序对为4+3+2+1 = 10

那么对于归并排序的求解过程：
第一层：

1.1：5 4 3

1.2：2 1

第二层：

2.1.1： 5 4

2.1.2： 3

2.2.1： 2 

2.2.2： 1

 

第三层：

3.1.1.1 ：5

3.1.1.2 ：4

3.1.2： 3

3.2.1： 2 

3.2.2： 1

 

第三层归并后：
4 5

3

2

1

第二层归并后
3 4 5

1 2

第一层归并后

1 2 3 4 5

 

那么对于逆序对的求解：

每一层的求解的是该层被归并的两个集合存在的逆序对数量

那么由于该层的两个集合已经内部有序了，故如果存在

(mid + 1, r)集合中第i个元素，比(l, mid)集合中的第j个元素小，那么答案加上(mid - j + 1)即可

 

归并模板:
 

void merge_sort(int q[], int l, int r){
    if(l >= r) return ;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if(q[i] <= q[j]) t[k++] = q[i++];
        else t[k++] = q[j++];
    }
    
    while(i <= mid) t[k++] = q[i++];
    while(j <= r) t[k++] = q[j++];
    
    for(i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
}

 

Acwing788 求逆序对：
ACcode:
 

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100010;
int q[N], t[N];
int n;
ll ans = 0;

void merge_sort(int q[], int l, int r){
    if(l >= r) return ;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if(q[i] > q[j]){
            ans += (mid - i + 1);
            t[k++] = q[j++];
        }
        else t[k++] = q[i++];
    }
    
    while(i <= mid) t[k++] = q[i++];
    while(j <= r) t[k++] = q[j++];
    
    for(i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &q[i]);
    
    merge_sort(q, 1, n);
    
    printf("%lld\n", ans);
    
    return 0;
}