所以实现一个归并排序的代码为：
private static void mergesort(int[] array, int left, int right) {int mid=(left+right)/2;
if(left<right)
{
mergesort(array, left, mid);
mergesort(array, mid+1, right);
merge(array, left,mid, right);
}
}
private static void merge(int[] array, int l, int mid, int r) {
int lindex=l;int rindex=mid+1;
int team[]=new int[r-l+1];
int teamindex=0;
while (lindex<=mid&&rindex<=r) {//先左右比较合并
if(array[lindex]<=array[rindex])
{
team[teamindex++]=array[lindex++];
}
else {
team[teamindex++]=array[rindex++];
}
}
while(lindex<=mid)//当一个越界后剩余按序列添加即可
{
team[teamindex++]=array[lindex++];
}
while(rindex<=r)
{
team[teamindex++]=array[rindex++];
}
for(int i=0;i<teamindex;i++)
{
array[l+i]=team[i];
}
}
逆序数
首先得了解什么是逆序数：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对
也就是比如3 2 1.看3 ，有2 1在后面，看2 有1在后面有3个逆序数。
而比如1 2 3的逆序数为0.
在数组中，暴力确实可以求出逆序数，但是暴力之法太复杂，不可取！而有什么好的方法能解决这个问题呢？ 当前序列我可能不知道有多少序列。但是我们直到如果这个序列如果有序那么逆序数就为0.
在看个序列 abcd 3 2 1 efg编程abcd 1 2 3 efg整个序列逆序数减少3个。因为如果不管abcd还是efg和123三个数相对位置没有变。所以我们是可以通过某种方法确定逆序数对的。
我们就希望能不能有个过程，动态改变如果逆序数发生变化能够记录下来？！比如动那么一下能够知道有没有改变的。并且这个动不能瞎动，***是局部的，有序的动。归并排序就是很适合的一个结构。因为肯定要选个小于O(n^2^)的复杂度算法，而归并排序满足，并且每次只和邻居进行归并，归并后该部分有序。
纵观归并的每个单过程例如两个有序序列：假设序列2 3 6 8 9和序列1 4 7 10 50这个相邻区域进行归并。
而纵观整个归并排序。变化过程只需要注意一些相对变化即可也就是把每个归并的过程逆序数发生变化进行累加，那么最终有序的那个序列为止得到的就是整个序列的逆序数！
