（二路）归并排序

什么是归并排序，顾名思义，归并简单理解成合并多个序列，归并排序也就是归并多个有序序列。这里讨论的是二路归并排序，二路是指将未排序的序列一分为二，分别排序后合二为一（也就是归并两个序列）。实现归并排序有两种方法，一种是递归，而是非递归。

递归方法

public static void sort(int[] arr) {
       mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int low, int high) {
        int m;
        if (low < high) {
            m = (low + high) / 2;
            mergeSort(arr, low, m);
            mergeSort(arr, m + 1, high);
            merge(arr, low, m, high);
        }
}

    public static void merge(int[] arr, int low, int m, int high) {
        int k, j;
        int[] temp = new int[arr.length];
        System.arraycopy(arr, low, temp, low, high - low + 1);
        for (k = low, j = m + 1; low <= m && j <= high; k++) {
            if (temp[low] < temp[j]) {
                arr[k] = temp[low++];
            } else {
                arr[k] = temp[j++];
            }
        }
        if (low > m) {
            System.arraycopy(temp, j, arr, k, high - j + 1);
        }
        if (j > high) {
            System.arraycopy(temp, low, arr, k, m - low + 1);
        }
    }

测试

    public static void main(String[] args) throws IOException {
        int[] arr = {1, 0, 12, 45, 21, 78, 628, 45, 36, 97, 15, 65, 45, 24, 10, 74, 58, 69, 25, 46, 36, 39, 48, 43, 19, 18};
        int[] temp = new int[arr.length];
        sort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

缺点： merge方法第4行的System.arraycopy(arr, low, temp, low, high - low + 1)，每一层递归复制n次，时间复杂度 nlogn

优化

每一次递归都创建一个tempArr2对象用于保存本次排序的未归并结果，然后传递给归并方法，避免以上所说的缺点，时间复杂度为n由下面第11行代码tempArr[low] = arr[low]可以看出来一共只执行n次，相比每一层递归都复制n次，这个优化对于提高算法效率还是很重要。

    public static void mergeSort(int[] arr, int[] tempArr, int low, int high) {
        int[] tempArr2 = new int[arr.length];
        int m;
        if (low < high) {
            m = (low + high) / 2;
            mergeSort(arr, tempArr2, low, m);
            mergeSort(arr, tempArr2, m + 1, high);
            merge(tempArr2, tempArr, low, m, high);
        } else {
            tempArr[low] = arr[low];
        }
    }
    public static void merge(int[] arr, int[] temp, int low, int m, int high) {
        int k, j;
        for (k = low, j = m + 1; low <= m && j <= high; k++) {
            if (arr[low] < arr[j]) {
                temp[k] = arr[low++];
            } else {
                temp[k] = arr[j++];
            }
        }
        if (low > m) {
            System.arraycopy(arr, j, temp, k, high - j + 1);
        }
        if (j > high) {
            System.arraycopy(arr, low, temp, k, m - low + 1);
        }
    }

非递归方法

递归方法实质是递归到最底层然后逐层向上归并，那么也可以一开始就直接从最底层逐层向上归并，这样更加省时间，免去了递归的损耗。

    public static void sort(int[] arr) {
        int k = 1;
        int[] temp = new int[arr.length];
        while (k < arr.length) {
            mergePass(arr, temp, k, arr.length);
            k = 2 * k;
            mergePass(temp, arr, k, arr.length);
            k = 2 * k;
        }
    }
    public static void mergePass(int[] SR, int[] TR, int s, int n) {
        int i = 0;
        int j;
        while (i + 2 * s < n) {
            merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
            i = i + 2 * s;
        }
        if (i + s - 1 < n - 1) {
            merge(SR, TR, i, i + s - 1, n - 1);
        } else {
            for (j = i; j < n; j++)
                TR[j] = SR[j];
        }
    }
    public static void merge(int[] arr, int[] temp, int low, int m, int high) {
        int k, j;
        for (k = low, j = m + 1; low <= m && j <= high; k++) {
            if (arr[low] < arr[j]) {
                temp[k] = arr[low++];
            } else {
                temp[k] = arr[j++];
            }
        }
        if (low > m) {
            System.arraycopy(arr, j, temp, k, high - j + 1);
        }
        if (j > high) {
            System.arraycopy(arr, low, temp, k, m - low + 1);
        }
    }

总结

在递归方法的第一个算法里面，为了省去方法的参数直接将排序结果作用于原数组，这就导致每一归并都要进行复制，比传递排序序列的方法多了一步，导致没必要的耗时，所以在解决之类问题时，没有必要一味追求程序的简洁，而是应该考虑到算法的效率。