核心思想

如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

采用分治（Divide-and-conquer）的思想，用递归的方式来实现。

算法描述

算法：mergeSort(s, n)

输入：n 个元素组成的无序序列 s

输出：经排序，s 成为有序序列

{
    if (1 < n)  { // 不超过一个元素组成的序列 s 必然有序，故可直接返回 s
        s1 = s[0..[n/2]-1];     s2 = s[[n/2]..n-1]; // 将 s 尽可能均匀地分为前后两个子序列
        mergeSort(s1, [n/2]);   mergeSort(s2,[n/2]);    // 经过递归，分别对两个子序列进行排序
        s = merge(s1, s2);      // 将两个有序子序列归并得到有序序列 s
    }
    return s;
}

递推公式

// 递推公式
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

// 终止条件
p >= r // 不用再继续分解

merge_sort(p..r)表示，给下标从 p 到 r 之间的数组排序。

将这个排序问题转化成两个子问题， merge_sort(p...q) 和 merge_sort(q+1...r), 其中下标 q 等于 p 和 r 的中间位置，也就是 (p+r)/2。

当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后， 再将两个有序的子数组合并在一起， 这样下标从 p 到 r 之间的数据也就排好序了。

/**
 * 归并排序算法，
 * @param a a是数组
 * @param n n表示数组大小
 */
public static void mergeSort(int[] a, int n){
    mergeSortInternally(a, 0, n-1);
    System.out.println(Arrays.toString(a));
}

/**
 * 递归调用函数
 *
 * @param a a是数组
 * @param p 数组开始位置
 * @param r 数组结束位置
 */
private static void mergeSortInternally(int[] a, int p, int r){
    // 递归终止条件
    if (p >= r) { return;}

    // 取p到r之间的中间位置q，防止(p+r)的和超过int类型最大值
    int q = p + (r - p)/2;

    // 分治递归
    mergeSortInternally(a, p, q);
    mergeSortInternally(a, q+1, r);

    // 将A[p...q]和A[q+1...r]合并为A[p...r]
    merge(a, p, q, r);
}

合并过程

merge(a, p, q, r)函数的作用就是将已经有序的A[p...q]和A[q+1...r]合并成一个有序的数组，并且放入A[p...r]。

private static void merge(int[] a, int p, int q, int r) {
    int i = p;
    int j = q+1;
    int k = 0;  // 初始化变量i, j, k
    int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
    while (i<=q && j<=r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];  // i++等于i:=i+1
        } else {
            tmp[k++] = a[j++];
        }
    }

    // 判断哪个子数组中有剩余的数据
    int start = i;
    int end = q;
    if (j <= r) {
        start = j;
        end = r;
    }

    // 将剩余的数据拷贝到临时数组tmp
    while (start <= end) {
        tmp[k++] = a[start++];
    }

    // 将tmp中的数组拷贝回a[p...r]
    for (i = 0; i <= r-p; ++i) {
        a[p+i] = tmp[i];
    }
}

申请一个临时数组tmp，大小与A[p...r]相同。 用两个游标 i 和 j，分别指向A[p...q]和A[q+1...r]的第一个元素。 比较这两个元素A[i]和A[j]， 如果A[i]<=A[j]，就把A[i]放入到临时数组 tmp，并且 i 后移一位， 否则将 A[j] 放入到数组 tmp，j 后移一位。

继续上述比较过程，直到其中一个数组中的所有数据都放入临时数组中， 再把另一个数组中的数据依次加入到临时数组的末尾， 这个时候，临时数组中存储的就是两个子数组合并之后的结果了。 最后再把临时数组 tmp 中的数据拷贝到原数组 A[p...r]中。

哨兵机制

merge()合并函数借助哨兵，代码就会简洁很多。

/**
 * 合并（哨兵）
 *
 * @param arr a是数组
 * @param p 数组开始位置
 * @param q 取p到r之间的中间位置q，防止(p+r)的和超过int类型最大值
 * @param r 数组结束位置
 */
private static void mergeBySentry(int[] arr, int p, int q, int r) {
    int[] leftArr = new int[q - p + 2];
    int[] rightArr = new int[r - q + 1];

    for (int i = 0; i <= q - p; i++) {
        leftArr[i] = arr[p+i];
    }

    // 第一个数组添加哨兵（最大值）
    leftArr[q-p+1] = Integer.MAX_VALUE;

    for (int i = 0; i < r - q; i++) {
        rightArr[i] = arr[q+1+i];
    }
    // 第二个数组添加哨兵（最大值）
    rightArr[r-q] = Integer.MAX_VALUE;

    int i = 0;
    int j = 0;
    int k = p;
    while (k <= r) {
        // 当左边数组到达哨兵值时，i不再增加，直到右边数组读取玩剩余值，同理右边数组也一样
        if (leftArr[i] <= rightArr[j]){
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }
}

性能分析

归并排序是一个稳定的排序算法。

归并排序的时间复杂度为O(nlogn)，其执行效率与要排序的原始数组的有序程度无关。

归并排序的空间复杂度为O(n)。 在任意时刻，CPU只会有一个函数在执行，也就是只会有一个临时的内存空间在使用。 临时内存空间最大也不会超过n个数据的大小，所以空间复杂度是O(n)。

弱点

归并排序有一个致命的弱点，那就是它不是原地排序算法。