数据结构实现二路归并排序算法

二路归并排序是一种高效的排序算法，它采用了分治法的思想，将待排序数组分成两个独立的部分，分别对这两个部分进行排序，然后合并这两个有序部分。在数据结构中，常常使用两个辅助数组来存储中间结果，这样可以方便地进行归并操作。

以下是二路归并排序的基本步骤：

1. **分区操作（Partition）**: 将数组分为两部分，一部分包含所有小于或等于基准值的元素，另一部分包含所有大于基准值的元素。这个过程通常不是直接进行的，而是通过一趟比较和交换来实现。

2. **递归调用（Recursion）**: 对两个分区分别递归地执行同样的操作，直到每个分区只有一个元素或为空。

3. **合并操作（Merge）**: 当两个分区排序完毕后，将它们合并到一起。这里就是利用了额外的辅助数组，从两个分区的起始位置开始比较，较小的元素放入原数组中，直到其中一个分区完全填充，然后将另一个分区剩余的部分复制到原数组中。

4. **重复上述步骤直至整个数组排序完成**。

以下是使用数组（Array）实现的伪代码版本：

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);  // 分治左半部分
        mergeSort(arr, mid + 1, right);  // 分治右半部分
        merge(arr, left, mid, right);  // 合并两个部分
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int[] temp = new int[n1 + n2];

    // 提取左半部分到临时数组
    for (int i = 0; i < n1; i++)
        temp[i] = arr[left + i];
    // 提取右半部分到临时数组
    for (int j = 0; j < n2; j++)
        temp[n1 + j] = arr[mid + 1 + j];

    // 将临时数组中的元素按照顺序合并回原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (temp[i] <= temp[j]) {
            arr[k++] = temp[i++];
        } else {
            arr[k++] = temp[j++];
        }
    }

    // 如果左侧剩余元素，复制过去
    while (i < n1) {
        arr[k++] = temp[i++];
    }

    // 如果右侧剩余元素，复制过去
    while (j < n2) {
        arr[k++] = temp[j++];
    }
}