5、数据结构与算法——归并排序（1） - liuxiaofei2010S/special-column GitHub Wiki

归并操作指的是两个相互独立的有序数组合并成一个有序数组的过程。如果对一个数组递归地使用归并操作，就是归并排序。

首先，需要一个对数组进行归并操作的方法，其中需要原地归并。那么一般性地需要一个辅助数组，将原数组复制到辅助数组，然后在归并的时候赋值给原先数组。

归并操作方法代码如下：

public static void merge(int[] array, int lo, int mid, int hi) {
    for (int i = lo; i <= hi; i++) {
        aux[i] = array[i];
    }
    int m = lo, n = mid + 1;
    for (int t = lo; t <= hi; t++) {
        if (m > mid) array[t] = aux[n++];
        else if (n > hi) array[t] = aux[m++];
        else if (less(aux[m], aux[n])) array[t] = aux[m++];
        else array[t] = aux[n++];
    }
}

在归并操作地基础上，进行自顶而下的归并排序，那么代码如下：

public static void main(String[] args) {
    System.out.print("——————————————————————————————");
    int[] array = new int[]{4, 2, 8, 7, 11, 10, 9, 1, 3, 5, 6, 0, 12, 13, 14};
    aux = new int[array.length];
    sort(array, 0, array.length - 1);         //开始调用方法
    System.out.print("——————————————————————————————");
}

public static void sort(int[] array, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    sort(array, lo, mid);       //排序对应的下标之间的项，可能调用更下面的排序
    sort(array, mid + 1, hi);
    merge(array, lo, mid, hi);        //归并上面已经排序好的相互独立的两组数组
}

自顶而下的归并排序方法的运行时间为 NlgN，因此可以用来处理百万或者更大的数组。

但是缺点是辅助数组需要的额外空间和 N 的大小成正比。

另外，在数组规模为 15 以下的时候，可以使用 插入排序 或者 选择排序 来代替归并排序，以提高效率。