问题描述：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组 的小和。

例子： [1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16

问题求解：

首先描述Merge的过程。

类似于外排序，时间复杂度为O(n)。
例如A[]={1，3，4},B[]={2，5}，
A和B进行Merge时，有两个指针分别指向A[0]位置和B[0]位置，且生成一个辅助数组Help[A.length+B.length],例子中即为Help[5]。
首先依次比较A[0]和B[0]的大小，谁小填入Help数组中，且填入后该指针向后移动一位，直至任一指针到达数组边界，然后将另一个数组的未填入的数组全部填入Help数组中。最后，将Help数组的数据拷贝至原数组的位置，形成有序的序列。

由于Merge的过程中要对Merge的两个数组进行了比较，小和可以在Merge的过程中计算。
考虑使用归并排序解决。归并排序采用分治法，首先将一个数组分成左右规模相同的两个数组，再分，再分，直至分出的数组只有一个数字。接了来就是Merge的过程，通过外排序的方式依次拷贝数据至一个辅助数组中，如果左边数字较小，右边数字较大，此时产生小和。在进行组间Merge时，左右指针依次移动，如果左指针上的数字比右指针上的数字小，则产生（左指针上数字）*（右指针至边界数字的个数）的小和。如图所示，此处产生的小和为1*2=2。

上代码

package Sort;

public class SmallSum {
    public static int smallSum(int[] arr){
        if (arr.length<2&&arr==null){
            return 0;
        }
        return mergeSort(arr,0,arr.length-1);
    }
    public static int mergeSort(int[] arr,int L,int R){
        if(L==R){
           return 0;
        }
        int mid=L+((R-L)>>1);
        return mergeSort(arr,L,mid)
                +mergeSort(arr,mid+1,R)
                +merge(arr,L,mid,R);
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int[] help=new int[r-l+1];
        int p1=l;
        int p2=mid+1;
        int i=0;
        int res=0;
        while (p1<=mid&&p2<=r){
            res+=arr[p1]<arr[p2]?arr[p1]*(r-p2+1):0;
            help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while (p1<=mid){
            help[i++]=arr[p1++];
        }
        while (p2<=r){
            help[i++]=arr[p2++];
        }
        for (i=0;i<help.length;i++){
            arr[l+i]=help[i];
        }
        return res;
    }
}