归并排序详解（Merge Sort in Java）

1. 简介

本篇文章将带你深入理解 归并排序（Merge Sort）算法及其在 Java 中的实现方式。

归并排序是一种非常高效的排序方法，它基于 "分治思想（Divide and Conquer）" 实现。如果你追求稳定性和效率，尤其是在处理大规模数据时，归并排序是一个值得掌握的经典算法。

2. 算法原理

✅ 归并排序是一种典型的“分治”算法，它的核心思想是：

将原问题不断拆分成更小的子问题，直到每个子问题足够简单可以直接解决；
然后自底向上地合并这些子问题的解，最终得到完整问题的答案。

由于其天然的递归特性，归并排序非常适合用递归来实现。

整个过程可以分为两个阶段：

划分（Divide）阶段：
- 把数组从中间分成两部分；
- 对每一半继续递归划分，直到数组长度为 1。
合并（Conquer）阶段：
- 自底向上地将两个已排序的子数组合并成一个有序数组；
- 最终完成整个数组的排序。

来看一个例子：数组 {10, 6, 8, 5, 7, 3, 4} 的完整归并排序流程如下图所示：

从图中可以看到，数组被不断二分，直到只剩单个元素；然后开始合并，并在合并过程中进行排序，最终得到一个完全有序的数组。

3. Java 实现

我们来动手写一个归并排序的 Java 实现版本。

3.1 主函数 `mergeSort`

public static void mergeSort(int[] a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];

    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);

    merge(a, l, r, mid, n - mid);
}

这个函数的作用是：

如果数组长度小于 2，说明已经不能再拆分了，直接返回；
否则计算中点，创建左右两个临时数组；
分别复制原数组的前半段和后半段到这两个临时数组；
递归调用自身分别对左右两部分进行排序；
调用 merge() 方法将两个已排序的子数组合并回原数组。

3.2 合并函数 `merge`

public static void merge(int[] a, int[] l, int[] r, int left, int right) {
    int i = 0, j = 0, k = 0;

    // 比较左右数组中的元素，依次放入原数组
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        } else {
            a[k++] = r[j++];
        }
    }

    // 处理左数组剩余元素
    while (i < left) {
        a[k++] = l[i++];
    }

    // 处理右数组剩余元素
    while (j < right) {
        a[k++] = r[j++];
    }
}

这段代码逻辑清晰：

使用三个指针分别指向左子数组、右子数组和原数组；
依次比较左右数组当前元素，把较小的放到原数组；
当其中一个数组遍历完之后，将另一个数组剩下的元素直接追加到原数组末尾。

3.3 单元测试示例

@Test
public void positiveTest() {
    int[] actual = { 5, 1, 6, 2, 3, 4 };
    int[] expected = { 1, 2, 3, 4, 5, 6 };
    MergeSort.mergeSort(actual, actual.length);
    assertArrayEquals(expected, actual);
}

通过这个测试用例可以验证我们的归并排序是否正确运行。

4. 时间与空间复杂度分析

归并排序的时间复杂度可以通过递推关系表达为：

T(n) = 2T(n/2) + O(n)

其中：

2T(n/2) 表示对左右两个子数组分别进行排序所需时间；
O(n) 是合并两个子数组所需的线性时间。

解此递推式可得总时间复杂度为：

✅ O(n log n)

⚠️ 这个复杂度无论是在最好、最坏还是平均情况下都成立 —— 因为归并排序总是将数组平分成两部分，不会有极端情况。

空间复杂度方面：

❌ 归并排序并不是原地排序算法，每次递归都需要开辟新的临时数组用于存储子数组，因此空间复杂度为：

✅ O(n)

5. 总结

在这篇文章中，我们详细讲解了归并排序的基本原理以及如何在 Java 中具体实现。它是一种稳定的、时间复杂度恒定的排序算法，在很多场景下都非常实用。

虽然空间开销略高，但在需要稳定排序或外部排序（如磁盘文件排序）时，它仍然是首选之一。

完整源码可以在 GitHub 上找到：https://github.com/eugenp/tutorials/tree/master/algorithms-modules/algorithms-sorting

Persistence

REST

Security