【排序算法】自顶向下的归并排序

        归并：将两个有序的数组归并成一个更大的有序数组。

        要将一个数组排序，可以先递归的将它分成两半分别排序，然后将结果归并起来，这就是归并排序。归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比，它的主要缺点是它需要额外的与N成正比的空间。

        实现归并的一种直接了当的方法是将两个不同的有序数组归并到第三个数组中。实现的方法很简单，创建一个适当大小的数组然后将两个输入数组的元素一个个从小到大放入这个数组中。

        当归并将一个大数组排序时，我们需要进行很多次归并，因此在每次归并时都创建一个新数组来存储排序结果会带来问题。

        原地归并的数据抽象：

public static void merge(int[] a,int lo,int mid,int hi)
    {
        int i=lo,j=mid+1;
        for (int k=lo;k<=hi;k=k+1)
            aux[k]=a[k];
        for (int k=lo;k<=hi;k=k+1)
            if (i>mid)  a[k]=aux[j++];
            else if (j>hi)  a[k]=aux[i++];
            else if (aux[j]<aux[i])  a[k]=aux[j++];
            else   a[k]=aux[i++];
        list_deal.printArray(a);

    }

        基于原地归并的抽象实现了一种递归归并：

public class Merge {
    private static int [] aux;
    public static void sort(int[] a)
    {
        aux=new int[a.length];
        sort(a,0,a.length-1);
    }
    public static void merge(int[] a,int lo,int mid,int hi)
    {
        int i=lo,j=mid+1;
        for (int k=lo;k<=hi;k=k+1)
            aux[k]=a[k];
        for (int k=lo;k<=hi;k=k+1)
            if (i>mid)  a[k]=aux[j++];
            else if (j>hi)  a[k]=aux[i++];
            else if (aux[j]<aux[i])  a[k]=aux[j++];
            else   a[k]=aux[i++];
        list_deal.printArray(a);

    }

    private static void sort(int[] a ,int lo,int hi)
    {
        if (hi<=lo) return;
        int mid=lo+(hi-lo)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        merge(a,lo,mid,hi);

    }
    public static void main(String[] args) {
        int[] a={534,745,264,864,136,967,254,745,734,269,538,265,825,158,139,100};
        list_deal.printArray(a);
        sort(a);
        list_deal.printArray(a);
    }
}

排序过程：

534 745 264 864 136 967 254 745 734 269 538 265 825 158 139 100 
534 745 264 864 136 967 254 745 734 269 538 265 825 158 139 100 
534 745 264 864 136 967 254 745 734 269 538 265 825 158 139 100 
264 534 745 864 136 967 254 745 734 269 538 265 825 158 139 100 
264 534 745 864 136 967 254 745 734 269 538 265 825 158 139 100 
264 534 745 864 136 967 254 745 734 269 538 265 825 158 139 100 
264 534 745 864 136 254 745 967 734 269 538 265 825 158 139 100 
136 254 264 534 745 745 864 967 734 269 538 265 825 158 139 100 
136 254 264 534 745 745 864 967 269 734 538 265 825 158 139 100 
136 254 264 534 745 745 864 967 269 734 265 538 825 158 139 100 
136 254 264 534 745 745 864 967 265 269 538 734 825 158 139 100 
136 254 264 534 745 745 864 967 265 269 538 734 158 825 139 100 
136 254 264 534 745 745 864 967 265 269 538 734 158 825 100 139 
136 254 264 534 745 745 864 967 265 269 538 734 100 139 158 825 
136 254 264 534 745 745 864 967 100 139 158 265 269 538 734 825 
100 136 139 158 254 264 265 269 534 538 734 745 745 825 864 967 

        通过过程可以看到，递归归并的过程是将大数组不断分割为小数组，然后循环进行小数组排序、归并。

        对于长度为N的任意数组，自顶向下的归并排序需要进行1/2*NlogN至NlogN次比较。

        对于长度为N的任意数组，自顶向下的归并排序最多需要访问数组6NlogN次。

        对于小数组上，有可能插入排序（或者选择排序）比归并排序更快，所以，插入+递归归并有可能比全递归归并排序快，但是代码也更复杂。