相比树状数组求逆序对，归并排序的逻辑复杂度稍微小一点。
首先我们来理解归并排序。首先用mergeSort将一个序列不断二分，直到每个子序列只有长度2
然后递归到了栈底。我们再用merge函数，将递增有序的序列拼接起来。因为序列递增有序，所有时间复杂度为O( max(m+n) )，这里的m、n分别是两个序列的长度。加上二分，总的时间复杂度接近O(NlogN)
在拼接的过程中，用a、b分别记录两个序列的索引，然后不断取其中最小的。最后用两个while循环，将还满足“未越界”的a或b循环变量遍历完。最后，将临时数组放到arr工作数组中。
然后讨论怎样用这个过程求逆序数：
假设我们有两个递增有序的序列A和B：
Ａ：１ ３ ５
Ｂ：２ ４
循环取数的顺序是：１ ２ ３ ４ ５
加粗的表示取到了Ｂ序列。而这一过程中统计的逆序数的数目，就是Ａ的循环下标ａ的右端数的数目。
这很好理解：３、５都比２（当前Ｂ序列的数）大，５比４（当前Ｂ序列的数）大
牢记以上原则，就可以编写出求逆序对的代码。
板子：
int arr[LEN]; int tmp[LEN]; int ans=0; void merge(int s,int mid,int e){ int i=0,a=s,b=mid+1,j=0; while(a<=mid && b<=e){ if(arr[a]<=arr[b]){ tmp[i++]=arr[a++]; }else{ tmp[i++]=arr[b++]; ans+=mid-a+1; } } while(a<=mid) tmp[i++]=arr[a++]; while(b<=e) tmp[i++]=arr[b++]; FF(j,i) arr[s+j]=tmp[j]; } void mergeSort(int s,int e){ if(s<e){ //能够被划为。如果只有一个数就不能被划分 int mid=(s+e) /2; mergeSort(s,mid); mergeSort(mid+1,e); merge(s,mid,e); } }