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 N = a.length;
        copy = new int[N];
        for (int size = 1; size < N; size += size) {
            for (int lo = 0; lo < N - size; lo = lo + size + size)
                merge(a, lo, lo + size - 1, Math.min(lo + size + size - 1, N - 1));

        }
    }


    public static void main(String[] args) {
        int[] a = {12, 3, 9, 71};
        mergeSort(a);
        for (int i : a)
            System.out.print(i + ", ");
    }

}