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;
}
}
网友评论