一、归并排序（分治法）
分治法，顾名思义，先“分”后“治”。
分——分解子问题，直到能在O(1)时间复杂度解决，归并排序问题中即是将一个元素数目为N的序列分成单个元素（或者视为单个元素对象），所耗费的时间为log2 N。

数组[49, 38, 65, 97, 76, 13 ,27]
分解为下面初始序列：

治——归并排序，实时更新子序列排序状况，时间复杂度为N。

二、逆序对
逆序对：对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i<j 的有序对。
逆序数：一个排列所拥有逆序对的个数即为该排列的逆序数。

解题思路：在归并排序的基础上寻找逆序对；在每次合并之前，先计算逆序对数，左右两组数此时皆是从小到大的顺序排列。若左边第一个数大于右边第一个数，则左边剩下的数皆可和右边第一个数形成逆序对；此时继续看右边第二个数，比较左边第一个数和右边第二个数，以此类推。若左边第一个数小于右边第一个数，则比较左边第二个数和右边第一个数，如上述同样方式类推。

#include<bits/stdc++.h>
using namespace std;
int sum = 0;//记录逆序对的个数 
void MergeAndCount(int* num,int* result, int start, int end){int Lmark = start;int mid = (start + end)/2;int Rmark = mid;int rltmark = start;int temp1 = Lmark;int temp2 = Rmark;//基于现有排序计算逆序对的个数 while(temp1<mid && temp2<end){if(num[temp1] > num[temp2]){sum+= (mid-temp1);temp2++;}else{temp1++;}}//执行下一轮排序 while(Lmark<mid && Rmark<end){if(num[Lmark] >= num[Rmark]){result[rltmark] = num[Rmark];rltmark++;Rmark++;}else{result[rltmark] = num[Lmark];rltmark++;Lmark++;}}while(Lmark<mid){result[rltmark] = num[Lmark];rltmark++;Lmark++;} while(Rmark<end){result[rltmark] = num[Rmark];rltmark++;Rmark++;} }
void mergeSort(int* num,int* result, int start, int end){if(end - start == 1)//只有1个元素 return;	else{mergeSort(num, result, start, (start+end)/2);mergeSort(num, result,(start+end)/2,end);MergeAndCount(num,result,start,end);for(int i=start; i<end; i++)num[i] = result[i];}
}
int main()
{int n;cout<<"序列所含元素数目："<<endl;cin>>n;int *num = new int[n];int *result = new int[n];cout<<"输入元素："<<endl;for(int i=0;i<n;i++)cin>>num[i];mergeSort(num,result,0,n);cout<<"排序后的序列："<<endl; for(int i=0;i<n;i++)cout<<num[i]<<" ";cout<<endl;cout<<"该序列的逆序数："<<endl; cout<<sum<<endl;return 0;
}码片

运行结果：