public class MergeSort {

    /*
    归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，
    即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。
     */

    // 归并所需的辅助数组
    private static int[] aux;

    /**
     * 自顶向下的归并排序
     * @param a 待排序的数组
     * @param low 低位索引
     * @param high 高位索引
     */
    public static void mergeSort(int[] a, int low, int high) {
        // 一次性分配空间
        aux = new int[a.length];

        // 将数组a[low..high]排序
        if (low >= high)
            return;

        int mid = low + (high - low)/2;

        mergeSort(a, low, mid); // 将左半边排序
        mergeSort(a, mid+1, high); // 将右半边排序
        merge(a, low, mid, high); // 归并结果
    }

    // 原地归并
    public static void merge(int[] a, int low, int mid, int high) {
        // 将a[low..mid] 和 a[mid+1..high] 归并
        int i = low;
        int j = mid+1;

        // 将a[low..high]复制到aux[low..high]
        for (int k = low; k <= high; k++) {
            aux[k] = a[k];
        }

        // 归并回到a[low..high]
        for (int k = low; k <= high; k++) {
            if (i > mid)
                a[k] = aux[j++];
            else if (j > high)
                a[k] = aux[i++];
            else if (aux[i] > aux[j])
                a[k] = aux[j++];
            else
                a[k] = aux[i++];
        }
    }

    public static void main(String[] args) {
        int[] a = new int[] {2, 4, 7, 5, 11, 3, 1, 9, 7, 8, 10, 6, 2, -1, 0, -2};
        mergeSort(a, 0, a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}