排序算法丨归并排序

前言

归并排序(Merge Sort)，约翰·冯·诺伊曼在 1945 年提出，它是建立在归并操作上的一种有效、稳定的排序算法，因为归并对应的英文单词为 Merge，所以叫做归并排序。

排序思路

假设数组共有n个元素：

分解（Divide）：将 n 个元素分成个含 n/2 个元素的子数组（分解过程使用了二分的思想）；
解决（Conquer）：用合并排序法对两个子数组递归的排序；
合并（Combine）：合并两个已排序的子数组已得到排序结果。

具体步骤：
将待排序的数组不断地拆成两份，直到只剩下一个数字时，这一个数字组成的数组我们就可以认为它是有序的。然后将 1 个数字组成的有序数组合并成一个包含 2 个数字的有序数组，再将 2 个数字组成的有序数组合并成包含 4 个数字的有序数组...直到整个数组排序完成。

代码实现

这是最经典的归并排序，只需要一个二分拆数组的递归函数 mergeSort() 和一个合并两个有序列表的函数 merge() 即可。

public static void mergeSort(int[] arr) {
    if (arr.length == 0) {
        return;
    }
    int[] result = mergeSort(arr, 0, arr.length - 1);
    // 将结果拷贝到 arr 数组中
    for (int i = 0; i < result.length; i++) {
        arr[i] = result[i];
    }
}

// 对 arr 的 [start, end] 区间归并排序
private static int[] mergeSort(int[] arr, int start, int end) {
    // 只剩下一个数字，停止拆分，返回单个数字组成的数组
    if (start == end) {
        return new int[]{arr[start]};
    }
    int middle = (start + end) / 2;
    // 拆分左边区域
    int[] left = mergeSort(arr, start, middle);
    // 拆分右边区域
    int[] right = mergeSort(arr, middle + 1, end);
    // 合并左右区域
    return merge(left, right);
}

// 将两个有序数组合并为一个有序数组
private static int[] merge(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length + arr2.length];
    int index1 = 0, index2 = 0;
    while (index1 < arr1.length && index2 < arr2.length) {
        if (arr1[index1] <= arr2[index2]) {
            result[index1 + index2] = arr1[index1];
            index1++;
        } else {
            result[index1 + index2] = arr2[index2];
            index2++;
        }
    }
    // 将剩余数字补到结果数组之后
    while (index1 < arr1.length) {
        result[index1 + index2] = arr1[index1];
        index1++;
    }
    while (index2 < arr2.length) {
        result[index1 + index2] = arr2[index2];
        index2++;
    }
    return result;
}

其中， mergeSort(int[] arr) 函数是对外暴露的公共方法，内部调用了私有的 mergeSort(int[] arr, int start, int end) 函数，这个函数用于对 arr 的 [start, end] 区间进行归并排序。

代码优化

要知道：在递归过程中，函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成后返回时，才出栈。一旦递归的数据规模很大，就可能会造成堆栈溢出。

为了减少在递归过程中不断开辟空间的问题，可以在归并排序之前，先开辟出一个临时空间，在递归过程中统一使用此空间进行归并即可。

public static void mergeSort(int[] arr) {
    if (arr.length == 0) return;
    int[] result = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, result);
}

// 对 arr 的 [start, end] 区间归并排序
private static void mergeSort(int[] arr, int start, int end, int[] result) {
    // 只剩下一个数字，停止拆分
    if (start == end) return;
    int middle = (start + end) / 2;
    // 拆分左边区域，并将归并排序的结果保存到 result 的 [start, middle] 区间
    mergeSort(arr, start, middle, result);
    // 拆分右边区域，并将归并排序的结果保存到 result 的 [middle + 1, end] 区间
    mergeSort(arr, middle + 1, end, result);
    // 合并左右区域到 result 的 [start, end] 区间
    merge(arr, start, end, result);
}

// 将 result 的 [start, middle] 和 [middle + 1, end] 区间合并
private static void merge(int[] arr, int start, int end, int[] result) {
    int end1 = (start + end) / 2;
    int start2 = end1 + 1;
    // 用来遍历数组的指针
    int index1 = start;
    int index2 = start2;
    while (index1 <= end1 && index2 <= end) {
        if (arr[index1] <= arr[index2]) {
            result[index1 + index2 - start2] = arr[index1++];
        } else {
            result[index1 + index2 - start2] = arr[index2++];
        }
    }
    // 将剩余数字补到结果数组之后
    while (index1 <= end1) {
        result[index1 + index2 - start2] = arr[index1++];
    }
    while (index2 <= end) {
        result[index1 + index2 - start2] = arr[index2++];
    }
    // 将 result 操作区间的数字拷贝到 arr 数组中，以便下次比较
    while (start <= end) {
        arr[start] = result[start++];
    }
}

此外，还可以优化一些小细节：

int middle = (start + end) / 2;

改为使用位运算右移(>>)：

int middle = (start + end) >> 1;

一是因为使用 (start + end) / 2 求中间位置容易溢出；二是因为右移1位与除以2的效果相同，且右移的运算速度更快。

动画演示

演示动画来源于Visualgo

从动图中可以看出，两个相同的元素 5 在排序后依然能保持相对顺序不变。

复杂度分析

归并排序的复杂度比较容易分析，拆分数组的过程中，会将数组拆分 logn 次，每层执行的比较次数都约等于 n 次，所以时间复杂度是 O(nlogn)。
空间复杂度是 O(n)，主要占用空间的就是我们在排序前创建的长度为 n 的 result 数组，显然不是就地排序。

速度比选择排序好得多，仅次于快速排序，为稳定排序算法；一般用于对总体无序，但是各子项相对有序的数组。

参考

知乎-【算法】排序算法之归并排序
 Github
LeetCode
程序员小灰