归并排序

优点:所需时间和NlogN成正比

缺点:需要额外的内存用来存储辅助数组

/**
 * Created by Administrator on 2016/10/8.
 */
public class MergeSort {
    private static int copy[];


    /*
       原地归并
     */
    private static void merge(int[] a, int l, int m, int h) {
        int i = l, j = m + 1;//i,j分别为左右数组的第一个
        for (int k = l; k <= h; k++)
            copy[k] = a[k];
        for (int k = l; k <= h; k++) {
            if (i > m) a[k] = copy[j++];//左边取完
            else if (j > h) a[k] = copy[i++];//右边取完
            else if (copy[i] > copy[j]) a[k] = copy[j++];//右边最小 小于 左边最小
            else a[k] = copy[i++];//右边最小 大于 左边最小
        }
    }

    private static void mergeSort(int[] a, int l, int h) {
        int m = (l + h) / 2;
        if (h <= l) return;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, h);
        merge(a, l, m, h);
    }

    private static void mergeSort(int[] a) {
        copy = new int[a.length];
        mergeSort(a,0,a.length-1);
    }

    public static void main(String[] args) {
        int[] a = {12,30,59,74,39,85,681,234,9444,55,46,39,1,69,2346,4545,55,31};
        mergeSort(a);
        for (int i : a)
            System.out.print(i + ", ");
    }

}