归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

归并排序的时间复杂度为O(N log N)，空间复杂度为T(N)

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

但是，用归并将一个大数组排序时，则需要进行很多次归并，如果每次归并都创建一个数组来存储排序结果，会带来问题，因为下面实现了一种能够在原地归并的、自顶向下的归并排序算法。伪代码如下：

public class MergeSort {

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

    public static void Sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    /**
     * 将数组a[lo...hi]排序
     * 
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] 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);
    }

    /**
     * 原地归并（避免将两个不同的有序数组归并到第三个数组中）的抽象方法
     * 
     * @param a
     * @param lo
     * @param mid
     * @param right
     */
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 将a[lo...mid]和a[mid+1...hi]归并
        int i = lo;
        int j = mid + 1;
        Comparable[] aux = new Comparable[a.length];

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

        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
            } else if (aux[i].compareTo(aux[j])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }
}