# MergeSort归并排序和利用归并排序计算出数组中的逆序对


//输入: [7,5,6,4]
//输出: 5


public class mergeSort {
public static void main(String args[]) {
mergeSort a = new mergeSort();
int[] numbers = new int[] {7,2,5,2,6,3,4,8};
a.merge(0, numbers.length-1, numbers);
for (int i : numbers) {
System.out.println(i);
}
}
public void merge(int left, int right, int[] numbers) {
if(left < right) {
int mid = (left + right)/2;
merge(left, mid, numbers);
merge(mid+1, right, numbers);;
mergeSort(left, right, numbers);
}
}
public void mergeSort(int left, int right, int[] numbers) {
//将数组分为左右两个部分，分别为[left, mid]和[mid+1, right]
int mid = (left + right)/2;
int i = left;
int j = mid + 1;
int[] temp = new int[right - left + 1];
for(int k = 0 ; k  numbers[j]) {
temp[k] = numbers[j];
j++;
}
//反之亦然
else {
temp[k] = numbers[i];
i++;
}
}
//最后将排好序的temp数组重新放入原数组当中，记得起始位置是从numbers数组的left开始，而不是0
for(int m = left, k = 0; m <= right; m++, k++) {
numbers[m] = temp[k];
}
}
}

//最终结果为：2,2,3,4,5,6,7,8

1. 将要排序的数组number的左右两个部分一定都是已经分别排好序了的，例如上图中需要排序的数组[4，5，7，8，1，2，3，6]， 将这个数组分为左右两个部分[4，5，7，8]和[1，2，3，6]，这两个数组是一定已经排好顺序了的。

2. 每个数字与其他数组都会正好比一次大小，例如上图中的数字4，它在这次的统计中，会跟1，2，3，6比，会发现有3组逆序对，而在那之后，这个4就再也不会跟这4给数字进行比较了，也就不会产生重复。

public class Merge_Sort {
public static void main(String args[]) {
Merge_Sort a = new Merge_Sort();
int[] numbers = new int[] {4,2,5,2,6,3,4,8};
int b = a.merge(0, numbers.length-1, numbers);
System.out.println(b);
}
public int merge(int left, int right, int[] numbers) {
if(left < right) {
int mid = (left + right)/2;
int count = merge(left, mid, numbers) + merge(mid+1, right, numbers);;
return mergeSort(left, right, numbers, count);
}
return 0;

}
public int mergeSort(int left, int right, int[] numbers, int count) {
int mid = (left + right)/2;
int i = left;
int j = mid + 1;
int[] temp = new int[right - left + 1];
for(int k = 0 ; k  numbers[j]) {
temp[k] = numbers[j];
j++;
//count计数代码添加如下
count = count + (mid - i + 1);
}
else {
temp[k] = numbers[i];
i++;
}

}
for(int m = left, k = 0; m <= right; m++, k++) {
numbers[m] = temp[k];
}
return count;
}
}
//输出结果为8