public class MergeSort {

    /*
    歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，
    即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的，然后再把有序子序列合并為整體有序序列。
     */

    // 歸并所需的輔助數(shù)組
    private static int[] aux;

    /**
     * 自頂向下的歸并排序
     * @param a 待排序的數(shù)組
     * @param low 低位索引
     * @param high 高位索引
     */
    public static void mergeSort(int[] a, int low, int high) {
        // 一次性分配空間
        aux = new int[a.length];

        // 將數(shù)組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); // 歸并結(jié)果
    }

    // 原地歸并
    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]復(fù)制到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] + " ");
        }
    }

}