排序都用Qsort了，别的排序算法不怎么用，但有些排序的思想很重要。碰到一道求逆序对的题，要用到归并排序，学习了一下归并排序。
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
分解：将n个元素分成个含n/2个元素的子序列。
解决：用合并排序法对两个子序列递归的排序。
合并：合并两个已排序的子序列已得到排序结果。
算法很其的关键应该在如何合并上，这一点算法导论上讲的很清楚。
void Merge(int Left,int Middle,int Right)
{
int n1=Middle-Left+1; //Left到Middle的元素个数
int n2=Right-Middle; //Middle+1到Right的元素个数
for(int i=1;i<=n1;i++)
L[i]=A[Left+i-1]; //把Left到Middle的左堆元素复制到L数组中，已排好序
for(int i=1;i<=n2;i++)
R[i]=A[Middle+i]; //把Middle+1到Right的右堆中的元素复制到R数组中
L[n1+1]=M; // 底部存放“哨兵”，避免比较式判空，很巧
R[n2+1]=M;
int i=1;int j=1;
for(int k=Left;k<=Right;k++) // 每次把两堆中最小的元素复制到数组A中，这样合并成有序的序列
{
if(L[i]<=R[j])
{
A[k]=L[i];
i++;
}
else
{
A[k]=R[j];
j++;
}
}
}
递归的合并排序，如果子数组中至多有一个元素，当然是已排好，否则分解。
void Merge_sort(int Left,int Right)
{
int Middle;
if(Left<Right)
{
Middle=(Left+Right)/2;
Merge_sort(Left,Middle); // 二分分解左部分
Merge_sort(Middle+1,Right); // 二分分解有部分
Merge(Left,Middle,Right); //合并两部分
}
}
算法一直把序列分解，最后算法将自底向上两个长度为一的序列合并成已排好序的，接着将长度为2的序列合并成长度为4的有序序列，等等。一者合并成长度为n的有序序列。
在归并排序算法中稍作修改，就可以在nlog2(n)的时间内求逆序对。
将数组A[1...size]，划分为A[1...mid] 和 A[mid+1...size].那么逆序对数的个数为 f(1, size) = f(1, mid) + f(mid+1, size) + s(1, mid, size)，这里s(1, mid, size)代表左值在[1---mid]中，右值在[mid+1, size]中的逆序对数。由于两个子序列本身都已经排序，所以查找起来非常方便。
void Merge(int Left,int Middle,int Right)
{
int n1=Middle-Left+1;
int n2=Right-Middle;
for(int i=1;i<=n1;i++)
L[i]=A[Left+i-1];
for(int i=1;i<=n2;i++)
R[i]=A[Middle+i];
L[n1+1]=M;
R[n2+1]=M;
int i=1;int j=1;
for(int k=Left;k<=Right;k++)
{
if(L[i]<=R[j])
A[k]=L[i++];
else
{
A[k]=R[j++];
cunt+=n1-i+1; //cunt为全局变量
}
}
}
最后cunt即为逆序对的个数。