归并排序
归并排序的想法就是将一个数组分成两个小数组，每个小数组分别排好序。然后将其按顺序合并到一个新的数组中，这个数组就是所求的数组
private static void merge(int []a,int low,int mid,int high) {
int i=low;
int j=mid+1;
for(int k=low;k<=high;k++) {
b[k]=a[k];
}
for(int k=low;k<=high;k++) {
if(i>mid) a[k]=b[j++];
else if(j>high)a[k]=b[i++];
else if(b[i]<b[j]) a[k]=b[i++];
else a[k]=b[j++];
}
}
注意这里的b[low]-b[mid]和b[mid+1]-b[high]，b数组是a数组的复制数组，而这两个其实这个是看作成两个数组了。这两个数组一定是要排序（升序）好了。其实很有趣，所谓的合并就是就是比较这两个数组，打擂台。相对较小的元素，则赋值到a数组当中。
但是如何保证b[low]-b[mid]和b[mid+1]-b[high]都是排序好呢？一种方式是用之前的排序方式将b[low]-b[mid]和b[mid+1]-b[high]分别排序。第二种方式使用迭代分解的方式进行归并排序。
public class Mergesort {
private static int []b;
public static void sort(int []a) {
b=new int[a.length];
sort(a,0,a.length-1); //high是a.length-1
}
private static void sort(int []a,int low,int high) {
if(high<=low)return;
int mid=low+(high-low)/2;
sort(a, low, mid);
sort(a, mid+1, high);
merge(a, low, mid, high);
}
private static void merge(int []a,int low,int mid,int high) {
int i=low;
int j=mid+1;
for(int k=low;k<=high;k++) {
b[k]=a[k];
}
for(int k=low;k<=high;k++) {
if(i>mid) a[k]=b[j++]; //其中一方没有元素了，另一方’不战而胜‘
else if(j>high)a[k]=b[i++];
else if(b[i]<b[j]) a[k]=b[i++]; //比谁小，‘胜者为王’
else a[k]=b[j++];
}
}
}
这时候需要借助灵魂画手来分析sort是如何工作的。
sort迭代分析图.png
由图可见，迭代的过程中是对数组元素不断地二分，最后将会拆成一个个元素。然后开始回溯Merge，从合并（排序）两个元素开始，慢慢合并的两个数组的元素数越来越多，最终合并成一个数组。
其实sort还有其他一种方法，上面一种方法我们是对一个数组不断进行拆分，这种其实是一种自顶向下的一种看问题的方法。其实我们可以从底向上，直接就从底部看起，直接就合并数组，说实话这个循环很妙，我都想不到
private static void sort2(int []a) {
int n=a.length;
b=new int [n];
for(int size=1;size<n;size*=2) {
for(int low=0;low<n-size;low+=(size*2))
merge(a, low, low+size-1, Math.min(low+size*2-1, n-1));
}
}
这里的size从1开始，遍历原数组，让原数组分成一组组小数组，一组数组由两个长度为1的数组组成，然后进行合并排序操作。然后size逐渐变大，然后合并排序的数组就越来越大了，合并的时候始终保证的合并双方的数组都是排序的
归并排序好像速度和希尔排序差不了多少。
