package 排序算法;

public class MergerSort {
    public static void main(String[] args) {
        int[] arr= {3,2,5,6};
        System.out.println(mergerSort(arr));
        System.out.println();
    }
    public static int mergerSort(int[] arr) {
        if(arr==null||arr.length<2) {
            return 0;
        }
        int res=mergerProcess(arr, 0, arr.length-1);
        return res;
    }
    public static int mergerProcess(int[] arr, int L, int R) {
        if(L==R) {
            return 0;
        }
        int mid=(L+R)/2;
        return mergerProcess(arr, L, mid)+
               mergerProcess(arr, mid+1, R)+
               merger(arr, L, mid, R);
    }
    public static int merger(int[] arr, int l, int mid, int r) {
        int i=0;
        int p1=l;
        int p2=mid+1;
        int[] help = new int[r-l+1];
        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(int k=0;k<help.length;k++) {
            arr[l+k]=help[k];
        }
        return res;
    }
}