归并排序

阅读经典——《算法导论》02

不同算法中往往蕴含着通用的思想，分治法就是最常用的一种。

分治法使用递归的方式，将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解从而得到原问题的解。

仍然考虑排序问题，本文将要介绍的归并排序就是使用分治法的典型案例。

思路：
把待排序数组从中间分割为两个子数组，这两个子数组分别排序，排完序后再把它们合并起来。该思路的关键在于子数组如何排序，以及如何把排完序的两个子数组合并起来。

第一个问题，分治法的精髓就在于把大问题分解为小问题，因此子数组仍然要使用归并排序，这是一个递归的过程。递归结束的条件是问题不能进一步分解，即数组只有一个元素。

第二个问题，排完序的两个子数组只需要同时遍历一遍就可以合并起来，这不是什么困难的事情。

整个算法从细分到合并的详细过程如下图所示。

归并排序分解步骤

归并排序的动画演示如下图：

归并排序

算法：

/**
 * 归并排序，排序结果仍保存于arr数组中。
 * @param arr 需要排序的数组
 */
public void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
}

/**
 * 归并排序，排序arr数组中[p..r]的子数组，排序结果仍保存于arr数组中。
 * @param arr 需要排序的数组
 * @param p 待排序数组的起始下标
 * @param r 待排序数组的终止下标
 */
public void mergeSort(int[] arr, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(arr, p, q);
        mergeSort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}

/**
 * 归并已排序的两个子序列。
 * @param arr 待归并的序列
 * @param p 第一个子序列的起始下标
 * @param q 第一个子序列的结束下标
 * @param r 第二个子序列的结束下标
 */
public void merge(int[] arr, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int[] arrL = new int[n1 + 1];
    int[] arrR = new int[n2 + 1];
    for (int i=0; i<n1; i++) {
        arrL[i] = arr[p + i];
    }
    for (int i=0; i<n2; i++) {
        arrR[i] = arr[q + 1 + i];
    }
    arrL[n1] = Integer.MAX_VALUE;
    arrR[n2] = Integer.MAX_VALUE;
    int i = 0;
    int j = 0;
    for (int k = p; k <= r; k++) {
        if (arrL[i] <= arrR[j]) {
            arr[k] = arrL[i];
            i++;
        }
        else {
            arr[k] = arrR[j];
            j++;
        }
    }
}

mergeSort是用于递归调用的归并排序函数，merge是用于合并已排序序列的函数。它们的详细用法在代码注释里已经写得很清楚，此处不再赘述。

完整代码请参考MergeSort.java。

分析：
最后分析一下该算法的时间复杂度。归并排序采用了二等分的分治策略，因此每一级分治使问题规模减小一半，所以直到问题规模减小到1时应该经历了lgn级分治。每一级的归并操作需要Θ(n)的执行时间，因此总执行时间为Θ(nlgn)。

与上一篇文章提到的插入排序相比，归并排序的时间复杂度已经降低了很多，在输入规模n很大的情况下，两者的耗时差距非常大。

关注作者或文集《算法导论》，第一时间获取最新发布文章。

获取文集中的全套源码请访问GitHub代码仓库Algorithm。