归并排序算法

//归并排序  思想就是分成左右两边 分别排序 排好序过后进行一个归并过程  时间复杂度O(n*logn)
	public static 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,mid,right);
	}
	public static void Merge(int arr[],int left,int mid,int right){
		int help[]=new int[right-left+1];
		int index1=left,index2=mid+1,i=0;
		while(index1<=mid && index2<=right){
			help[i++]= arr[index1]<arr[index2]?arr[index1++]:arr[index2++];
		}
		while(index1<=mid){
			help[i++]=arr[index1++];
		}
		while(index2<=right){
			help[i++]=arr[index2++];
		}
		arr=help;
	}

求小和 如果一个数 比左边的数要大那么它就要加上左边比自己小的数 遍历完整个数组 求得的和就是小和
小和问题用归并算法求小和问题：我们可以看成一个数 左边有多少数比他大 那么就有多少个自己需要被加上
如果我们利用归并排序在每次比较大小的时候我们右边的数比左边的数大的时候，那么我们就需要加上右边的数从自己的当前坐标开始到数组尾部所包含数的个数和左边的数相乘的积
这样我们就可以节省许多的时间 时间复杂段编程的 O(n*logn)

public class getSmallSum {
	public static void main(String[] args){
		int arr[]=new int[]{1,2,3,4,5};
		System.out.println(mergeSort2(arr,0,4));
	}
	//求小和
	public static int mergeSort2(int arr[],int left,int right){
		if(left==right){
			return 0;
		}
		int mid=left+((right-left)>>1);	
		return mergeSort2(arr,left,mid) + mergeSort2(arr,mid+1,right) + Merge2(arr,left,mid,right);
	}
	public static int Merge2(int arr[],int left,int mid,int right){
		int help[]=new int[right-left+1];
		int index1=left,index2=mid+1,i=0,sum=0;
		while(index1<=mid && index2<=right){
			if(arr[index1]<arr[index2]){
				sum+=arr[index1]*(right-index2+1);
				help[i++]=arr[index1++];
			}else{
				help[i++]=arr[index2++];
			}
		}
		while(index1<=mid){
			help[i++]=arr[index1++];
		}
		while(index2<=right){
			help[i++]=arr[index2++];
		}
		arr=help;
		return sum;
	}
}

为什么排序后还是对的喃，因为我们的排序是分块的，每次排序后都会把当前块内小和求出来，所以不用担心会计算失误的情况。