概述

简单的来说, 归并就是将两个有序数列合并成一个有序数列.

归并排序就是利用归并的思想, 对待排序数组分成若干个长度为1的子数列, 然后将长度为1的数列进行两两合并, 得到若干个长度为2的有序数列, 在两两合并,得到长度为4的数列, 以此类推, 知道合并为1以数列, 结果就是排序好的数组.

其步骤正如上面所描述的一样:

1. 将数组分为若干个长度的为1的数组
2. 将长度为1的数组进行归并, 得到若干个长度为2的数组
3. 依次循环, 直到得到一个数组

其时间空间复杂度为:

Java代码实现

/**
 * 归并排序, 从小到大顺序
 * 
 * @param arr
 */
public void mergeSort(int[] arr) {
    /*
     * 1. 将数组分为若干个长度为1的子数列 
     * 2. 将若干个长度为1的数列合并成若干个长度为2的数列
     * 3. 将若干个长度为2的数列合并为若干个长度为4的数列
     * 4. 重复执行, 知道合并为1个数列
     */

    // 步长
    for (int size = 2; size < arr.length; size *= 2) {
        // 当前步长进行归并
        int i;
        for (i = 0; i < arr.length && (i + size - 1) < arr.length; i += size) {
            int middle = i + (size / 2) - 1;
            // 进行归并, i-middle (middle+1)-(i+size-1)
            merge(arr, i, i + size - 1, middle);
        }
        int middle = i + (size / 2) - 1;
        // 进行归并, i-middle (middle+1)-(arr.length-1)
        merge(arr, i, arr.length - 1, middle);
    }
    // 对最后的两个数组进行归并
    merge(arr, 0, arr.length - 1, arr.length / 2);
}

/**
 * 将两个数组归并为一个数组
 * 
 * @param arr
 * @param start
 *            开始位置索引
 * @param tail
 *            末尾位置索引
 * @param middle
 *            前一个数组末尾位置索引
 */
private void merge(int[] arr, int start, int tail, int middle) {
    int tmpMiddle = middle + 1;
    /**
     * 此处的临时数组,每次都要新建, 十分费时 同时也为GC带来负担 可以将其抽离为共用的一个数组, 每次使用同一个临时数组即可
     */
    // 临时数组
    int[] tmp = new int[tail - start + 1];
    for (int i = 0, j = start; i < tmp.length; i++) {
        // 前一个数组较小时
        if (tmpMiddle <= tail && j <= middle && arr[j] < arr[tmpMiddle]) {
            tmp[i] = arr[j];
            j++;
            // 后一个数组较小或相等时
        } else if (tmpMiddle <= tail && j <= middle && arr[j] >= arr[tmpMiddle]) {
            tmp[i] = arr[tmpMiddle];
            tmpMiddle++;
            // 都不满足时, 其中一个数组已经用尽了
        } else {
            if (j <= middle) {
                tmp[i] = arr[j];
                j++;
            } else if (tmpMiddle <= tail) {
                tmp[i] = arr[tmpMiddle];
                tmpMiddle++;
            }
        }
    }
    // 将排序后的数组赋值回数组中
    for (int i = 0, j = start; i < tmp.length; i++, j++) {
        arr[j] = tmp[i];
    }
}

一个简单的实现, 写的并不是很好, 各位参考一下即可!!