左边排好序，右边排好序，整体排好序

归并排序

private void mergeSort(int[] arr){
	if (null == arr || arr.length < 2){
		return;
	}
	mergeSort(arr,0,arr.length-1);
}


private void mergeSort(int[] arr, int left, int right){
	if (left == right){
		return;
	}
	int mid = left + ((right-left)>>1);
	mergeSort(arr, left, mid);
	mergeSort(arr, mid+1, right);
	merge(arr,left,right,mid);
}

private void merge(int[] arr, int left, int right, int mid){
	int pos1 = left;
	int pos2 = mid+1;
	int[] temp = new int[right-left+1];
	int index = 0;
	while(pos1<=mid&& pos2<=right){
		temp[index++] = arr[pos1] <= arr[pos2] ? arr[pos1++] : arr[pos2++];
	}
	while(pos1<=mid){
		temp[index++] = arr[pos1++];
	}
	while(pos2<=right){
		temp[index++] = arr[pos2++];
	}
	//将排序好的数组合并到原数组中
	//System.arraycopy(temp, 0, arr, left, temp.length);
	//上面的代码等价于
	for(int j=0; j<temp.length; j++){
		arr[left+j] = temp[j];
	}
}

小和问题

【题目】
在一个数组中，每一个数左边比当前数小的数字累加起来，叫做这个数组的小和。

【例子】
[1,3,4,2,5]，1左边比1小的数为0，3左边比3小的数，1；4左边比4小的数，1和3；2左边比2小的数字，2，5左边比5小的数字，1,3，4,2，所以小和为
1+1+3+1+1+3+4+2=16

【思路】
每次递归，左侧数据和右侧数据必定是已经排好序的，只是需要将两侧数据进行合并。所以当左侧a数据比右侧b数据小时，必定也小于b右侧的数据，假设参与整合排序的左侧数据是[1,3,6],右侧堆数据是，[2,4,5]，可以看出1比右侧的2小，那么1必定比2后面的数都小，所以需要加起来的1的个数是右侧数组里比1大的数据的个数,也就是3个，同理，3小于4，以及4后面的5，有2个，那么这部分的小和就是31+23=9

【代码】

private int getSmallSum(int[] arr){
	int sum = mergeSort(arr);
	System.out.print("小和是="+sum);
}

private int mergeSort(int[] arr){
	if(null == arr || arr.length < 2){
		return 0;
	}
	return mergeSort(arr, 0, arr.length-1);
}

private int mergeSort(int[] arr, int left, int right){
	if (left == right){
		return 0;
	}
	int mid = left + ((right-left)>>1);
	int sumLeft = mergeSort(arr, left, mid);
	int sumRight = mergeSort(arr, mid+1, right);
	int mergeSum = merge(arr, left, right, mid);
	return sumLeft+sumRight+mergeSum;
}

private int merge(int[] arr, int left, int right, int mid){
	int pos1 = left;
	int pos2 = mid + 1;
	int sum = 0;
	int[] temp = new int[right-left+1];
	int index = 0;
	while(pos1<=mid && pos2<=right){
		sum += arr[pos1]<arr[pos2] ? arr[pos1]*(right-pos2+1) : 0;
		temp[index++] = arr[pos1]<arr[pos2] ? arr[pos1++] : arr[pos2++];
	}
	while(pos1<=mid){
		temp[index++] = arr[pos1++];
	}
	while(pos2<=right){
		temp[index++] = arr[pos2++];
	}
	System.arraycopy(temp, 0, arr, left, temp.length);
	return sum;
}

逆序对

【题目】
在一个数组中，如果左边的数比右边的数大，则这两个数字构成一个逆序对，打印所有逆序对

【思路】
与归并排序类似，只不过是逆序,归并排序时按照由大到小的顺序排序，左侧和右侧作比较，左侧大于右侧某一数字时，必定也大于该数字右侧的所有数字。因为归并排序左右两侧必定是排好序的，倒序。

private void printInversion(int[] arr){
	mergeSort(arr);
}

private void mergeSort(int[] arr){
	if (null == arr || arr.length < 2){
		return;
	}
	mergeSort(arr, 0, arr.length-1);
}

private void mergeSort(int[] arr, int left, int right){
	if(left == right){
		return;
	}
	//此处一定记得加(),>>的优先级远低于+,如果没有括号或导致先算加号，再进行位运算
	int mid = left + ((right-left)>>1);
	mergeSort(arr, left, mid);
	mergeSort(arr, mid+1, right);
	merge(arr, left, right, mid);
}

private void merge(int[] arr, int left, int right, int mid){
	int[] temp = new int[right-left+1];
	int index = 0;
	int pos1 = left;
	int pos2 = mid + 1;
	while(pos1<=mid && pos2<=right){
		if (arr[pos1] > arr[pos2]){
			int len = right-pos2;//pos2包括pos2右侧的都是小于arr[pos1]的。
            int i = 0;
			while(i<=len){
				System.out.print(arr[pos1]+"-"+arr[pos2+i]+" , ");
				i++;
			}
			temp[index++] = arr[pos1++];
		} else {
			temp[index++] = arr[pos2++];
		}
	}
	while(pos1<=mid){
		temp[index++] = arr[pos1++];
	}
	while(pos2<=right){
		temp[index++] = arr[pos2++];
	}
	System.arraycopy(temp, 0, arr, left, temp.length);
}