《Java 归并排序：高效稳定的排序算法》

  一、归并排序简介

介绍归并排序是一种基于分治思想的经典排序算法，适用于各种规模的数据排序任务。 

二、算法原理

（一）分治策略

将未排序数组分割成两个子数组，递归地对子数组进行排序，最后合并成有序数组。

（二）关键步骤

1. 分割阶段：将数组分成两个子数组，通常是平均分割。
2. 递归排序：递归地对左右两个子数组进行排序。
3. 合并阶段：将排好序的子数组合并成一个新的有序数组。

（三）总体流程

1. 开始节点：表示归并排序算法开始执行。

2. 判断输入数组长度是否小于等于 1，如果是，则直接返回，这是一个判断节点。

3. 如果数组长度大于 1，则计算中间索引，将数组分为左右两个子数组，这是一个分割节点。

4. 对左右子数组分别递归调用归并排序，这是两个递归调用节点。

5. 当左右子数组都排序完成后，进行合并操作，这是一个合并节点。

6. 结束节点：表示归并排序完成。

三、代码示例

展示用 Java 实现归并排序的具体代码，包括分割、排序和合并的方法。

public class MergeSort {

    // 归并排序主方法
    public static void mergeSort(int[] arr) {
        // 如果数组为空或者长度小于等于 1，无需排序直接返回
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 创建一个与输入数组长度相同的临时数组，用于合并过程中的存储
        int[] temp = new int[arr.length];
        // 调用递归的归并排序方法，传入输入数组、临时数组、起始索引和结束索引
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    // 递归进行归并排序的方法
    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        // 如果起始索引小于结束索引，说明子数组长度大于 1，需要继续分割排序
        if (left < right) {
            // 计算中间索引
            int mid = left + (right - left) / 2;
            // 对左子数组进行归并排序，传入起始索引和中间索引
            mergeSort(arr, temp, left, mid);
            // 对右子数组进行归并排序，传入中间索引+1 和结束索引
            mergeSort(arr, temp, mid + 1, right);
            // 合并左右两个已排序的子数组
            merge(arr, temp, left, mid, right);
        }
    }

    // 合并两个已排序子数组的方法
    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        // i 用于遍历左子数组
        int i = left;
        // j 用于遍历右子数组
        int j = mid + 1;
        // k 用于遍历临时数组
        int k = left;

        // 当左子数组和右子数组都还有元素未处理时
        while (i <= mid && j <= right) {
            // 如果左子数组当前元素小于等于右子数组当前元素
            if (arr[i] <= arr[j]) {
                // 将左子数组当前元素放入临时数组，并移动左子数组指针
                temp[k++] = arr[i++];
            } else {
                // 将右子数组当前元素放入临时数组，并移动右子数组指针
                temp[k++] = arr[j++];
            }
        }

        // 如果左子数组还有元素未处理，将其全部放入临时数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 如果右子数组还有元素未处理，将其全部放入临时数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 将临时数组中的元素复制回原始数组
        for (int l = left; l <= right; l++) {
            arr[l] = temp[l];
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        mergeSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

四、算法分析

（一）时间复杂度

归并排序在所有情况下时间复杂度均为 O(nlogn)。

（二）空间复杂度

归并排序需要额外的 O(n)空间来保存临时数组。

（三）稳定性

归并排序是稳定的排序算法，相等元素的相对顺序在排序后不会改变。

五、应用场景

（一）大数据量排序

在处理大规模数据量的排序时表现出较好的性能和稳定性。

（二）外部排序

可轻松扩展到外部排序中，即在磁盘等外部存储器上进行排序操作。

（三）稳定性要求

适用于需要稳定性的排序任务。