归并过程（Merge Process）

1. 归并过程概述

在归并排序中，归并是排序过程中的核心步骤之一，它负责将两个已排序的子数组合并成一个新的有序数组。归并过程将排序的子问题合并成一个整体的排序结果。合并的过程中，我们依次比较左右两个子数组的元素，将较小的元素放入新数组中，直到一个子数组的元素完全合并进新数组，最后将剩余的另一个子数组中的元素直接放入新数组中。

1.1 归并过程的步骤

归并过程的具体步骤可以总结为以下几点：

初始化两个指针：首先，我们需要两个指针，分别指向左子数组和右子数组的起始位置。假设左子数组的大小为 ( m )，右子数组的大小为 ( n )，那么我们分别用 i 和 j 来表示这两个数组的当前元素位置。
比较元素大小：接着，我们从两个子数组的起始位置开始，比较它们指向的元素的大小。将较小的元素放入合并后的新数组中，并移动对应的指针。
处理剩余元素：如果一个子数组的所有元素已经全部被合并，而另一个子数组仍有元素未处理，那么直接将另一个子数组剩余的元素放入新数组中。
返回合并结果：当所有的元素都被合并到新数组中后，我们就得到了一个排好序的数组。

1.2 归并过程的特点

归并过程是稳定的排序操作，两个相同的元素在合并过程中保持相对顺序。
归并过程的时间复杂度是 O(n)，其中 n 是当前要合并的两个子数组的总长度。
归并过程中需要额外的空间来存储合并后的数组，因此空间复杂度是 O(n)。

2. 归并过程的Java代码实现

2.1 归并过程的Java代码

下面是实现归并过程的Java代码，展示如何将两个已经排好序的子数组合并成一个新的有序数组。

public class MergeProcess {

    // 合并方法：将两个已排序的数组合并成一个有序数组
    public static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // 比较并将较小的元素依次放入原数组中
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k++] = left[i++];  // 将左子数组的元素放入原数组
            } else {
                array[k++] = right[j++];  // 将右子数组的元素放入原数组
            }
        }

        // 如果左子数组还有剩余元素，直接将它们放入原数组
        while (i < left.length) {
            array[k++] = left[i++];
        }

        // 如果右子数组还有剩余元素，直接将它们放入原数组
        while (j < right.length) {
            array[k++] = right[j++];
        }
    }

    // 打印数组的方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();  // 输出换行
    }

    // 测试合并过程
    public static void main(String[] args) {
        int[] left = {2, 4, 6};  // 左子数组
        int[] right = {1, 3, 5};  // 右子数组
        int[] merged = new int[left.length + right.length];  // 合并后的数组

        merge(merged, left, right);  // 调用合并方法

        System.out.println("合并后的数组：");
        printArray(merged);  // 打印合并后的结果
    }
}

2.2 代码解析

merge方法：
- 这是归并过程的核心方法。输入参数包括：array 是最终的合并数组，left 是左子数组，right 是右子数组。
- 我们使用三个指针：i 用于遍历左子数组，j 用于遍历右子数组，k 用于填充合并后的新数组。
- 在 while (i < left.length && j < right.length) 循环中，我们不断比较左右两个子数组的当前元素，将较小的元素放入合并后的数组，并移动对应的指针。
- 如果某一子数组的元素全部被合并完毕，剩下的子数组的所有元素将直接放入合并后的数组中。
printArray方法：
- 用于打印数组中的元素，便于观察合并后的结果。
main方法：
- 我们创建了两个已排序的子数组 left 和 right，并通过调用 merge 方法将它们合并成一个有序的数组 merged。
- 最后，我们通过 printArray 方法打印合并后的数组，查看合并结果。