归并排序是采用分冶实现的，其核心思想就是分冶得到两边经过递归是有序的，（因为分到最后就是两个元素的比较。
举个例子 a[]={7 ,5, 3, 2, 6, 9, 4, 1}进行归并排序
1： sort（7 5 3 2） sort（6 9 4 1）
2：递归循环sort（7 5） sort(3 2)
看下归并怎么处理sort（7 5）.最后递归sort（7），sort（5）返回7 和5；7和5两个元素是有序的，a[0]=7;a[1]=5;新建数组b[2]; 5的序列标签为i;7的标签为j;其实这个都是0.但是5这边的元素小，所以b[0]=5;此时j ；b[1]=5;再将b数组的元素复制到a[0-1]中。
再看sort（7，5，3，2）经过递归处理a[]前四位变成{5，7，2，3}；依然是分左右两份处理。新建数组b[];左面标签i,右面j；5>2；b[0]=2; (j=1).又5>3;所以b[1]=3；右侧没元素，b[2]=5;b[3]=7;（这里ij只是表示左右位数的index）。再将a【】替换。
最后整个排序就完成了。这个就是牺牲空间提升速度（个人感觉）；
那么归并排序和逆序数有什么关系呢？
仔细观察序列。（7，5）一个逆序列。（3，2）3在二前面，一个逆序。总计两个。（5，7，2，3）2前面两个，三前面两个。总计2 4=6；你可以发现规律：逆序数 =左侧剩余元素数量（前提是当前最小为右侧元素，要操作右侧元素）。层层叠加，就形成了逆序数合。
附上代码如下：
杭电6318
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; public class Main { static long time=0; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); long n=0,x=0,y=0; while(in.nextToken() != StreamTokenizer.TT_EOF) { n=(int)in.nval;in.nextToken(); x=(int)in.nval;in.nextToken(); y=(int)in.nval; int a[]=new int[(int) n]; for(int i=0;i<n;i++) { in.nextToken(); a[i]=(int)in.nval; } time=0;long min=x<y?x:y; sort(a,0,a.length-1); long value=min*time; out.println(value); out.flush(); } } public static int[] sort(int a[],int left,int right) { int mid=(left+right)/2; if(left<right) { sort(a,left,mid); sort(a,mid+1,right); merge(a,left,mid,right);} return a; } private static void merge(int[] a, int left, int mid, int right) { int team[]=new int[right-left+1]; int i=left; int j=mid+1; int k=0; while(i<=mid&&j<=right) { if(a[i]<=a[j]) {team[k++]=a[i++];} else { team[k++]=a[j++];time+=mid-i+1; } } while(i<=mid) { team[k++]=a[i++]; } while(j<=right) { team[k++]=a[j++]; } for(int q=0;q<k;q++) { a[q+left]=team[q]; } } }
