本教程详细介绍了如何在java中实现递归归并排序，特别关注了在不依赖`arrays.copyofrange`等标准库方法的情况下，通过自定义逻辑进行数组切片。此外，文章还深入探讨了如何扩展传统的二路归并操作，实现高效的三路归并函数，并提供了完整的代码示例、注意事项及优化建议，旨在帮助读者掌握归并排序的核心原理及其在特定限制下的实现技巧。
1. 归并排序概述
归并排序（Merge Sort）是一种高效的、基于比较的排序算法，它采用分治法（Divide and Conquer）策略。其基本思想是将一个大数组递归地分成两个较小的子数组，直到子数组只包含一个元素（此时认为有序），然后将这些有序的子数组两两合并，最终得到一个完全有序的数组。
归并排序的关键在于“合并”（Merge）操作，它能将两个已排序的子数组合并成一个更大的有序数组。
2. 自定义数组切片方法
在标准Java开发中，我们通常使用Arrays.copyOfRange()方法来方便地获取数组的子范围。然而，在某些特定场景下，例如要求不使用任何标准库包或需要更精细的控制时，我们需要自行实现数组切片功能。
Arrays.copyOfRange(original, from, to)方法会复制original数组中从from（包含）到to（不包含）的元素。我们可以通过一个简单的循环来实现同样的功能：
立即学习“Java免费学习笔记（深入）”；
/**
* 自定义数组切片方法，模拟Arrays.copyOfRange的功能。
* 复制原始数组中从from（包含）到to（不包含）的元素。
*
* @param original 原始数组
* @param from 起始索引（包含）
* @param to 结束索引（不包含）
* @return 包含指定范围元素的新数组
*/
private static int[] copyArray(int[] original, int from, int to) {
// 新数组的长度为 to - from
int[] result = new int[to - from];
// 遍历原始数组的指定范围，并将元素复制到新数组中
for (int i = from; i < to; i++) {
result[i - from] = original[i]; // 确保新数组从索引0开始填充
}
return result;
}这个copyArray方法实现了与Arrays.copyOfRange相同的功能，它创建了一个新数组，并根据指定的起始和结束索引（from和to）将原始数组的相应部分复制到新数组中。
3. 递归归并排序实现
有了自定义的数组切片方法，我们现在可以构建不依赖Arrays.copyOfRange的递归归并排序算法。
public class MergeSort {
// 主方法，用于测试归并排序
public static void main(String[] args) {
// 示例输入
int[] inputArray = {38, 27, 43, 3, 9, 82, 10};
System.out.println("原始数组: " + java.util.Arrays.toString(inputArray));
mergeSort(inputArray);
System.out.println("排序后数组: " + java.util.Arrays.toString(inputArray));
// 示例三路归并
int[] arr1 = {1, 5, 9};
int[] arr2 = {2, 6, 10};
int[] arr3 = {3, 7, 11};
int[] merged3 = mergeArrays3(arr1, arr2, arr3);
System.out.println("三路归并结果: " + java.util.Arrays.toString(merged3));
}
/**
* 递归归并排序主函数。
* 对给定的整数数组进行原地排序。
*
* @param A 待排序的整数数组
*/
public static void mergeSort(int[] A) {
// 基本情况：如果数组长度小于2，则认为它已经有序，直接返回
if (A.length < 2) {
return;
}
// 计算数组的中间索引
int mid = A.length / 2;
// 使用自定义的copyArray方法创建左右子数组
// leftArray 包含从索引 0 到 mid-1 的元素
int[] leftArray = copyArray(A, 0, mid);
// rightArray 包含从索引 mid 到 A.length-1 的元素
int[] rightArray = copyArray(A, mid, A.length);
// 递归地对左右子数组进行排序
mergeSort(leftArray);
mergeSort(rightArray);
// 将已排序的左右子数组合并回原数组A
merge(A, leftArray, rightArray);
}
/**
* 自定义数组切片方法，模拟Arrays.copyOfRange的功能。
* 复制原始数组中从from（包含）到to（不包含）的元素。
*
* @param original 原始数组
* @param from 起始索引（包含）
* @param to 结束索引（不包含）
* @return 包含指定范围元素的新数组
*/
private static int[] copyArray(int[] original, int from, int to) {
int[] result = new int[to - from];
for (int i = from; i < to; i++) {
result[i - from] = original[i];
}
return result;
}
}在mergeSort方法中，我们首先检查数组长度是否小于2作为递归的基准情况。然后，计算中间点mid，并利用copyArray方法将原始数组A分成leftArray和rightArray。这两个子数组会递归地进行排序，最后通过merge函数将它们合并回原始数组A中。
4. 二路归并函数
merge函数是归并排序的核心，它负责将两个已排序的子数组合并成一个更大的有序数组。这里，我们实现一个原地合并的版本，直接将结果写入传入的第一个数组a中。
public class MergeSort {
// ... (previous methods: main, mergeSort, copyArray) ...
/**
* 二路归并函数，将两个已排序的子数组l和r合并到主数组a中。
*
* @param a 目标数组，合并后的结果将存储在此数组中
* @param l 左子数组（已排序）
* @param r 右子数组（已排序）
*/
public static void merge(int[] a, int[] l, int[] r) {
int i = 0, li = 0, ri = 0; // i用于a的索引，li用于l的索引，ri用于r的索引
// 当左右子数组都还有元素时，比较它们的首元素并将其较小者放入a中
while (li < l.length && ri < r.length) {
if (l[li] <= r[ri]) { // 使用 <= 确保排序的稳定性
a[i++] = l[li++];
} else {
a[i++] = r[ri++];
}
}
// 如果左子数组还有剩余元素，将其全部复制到a中
while (li < l.length) {
a[i++] = l[li++];
}
// 如果右子数组还有剩余元素，将其全部复制到a中
while (ri < r.length) {
a[i++] = r[ri++];
}
}
}这个merge函数通过三个指针i、li和ri分别跟踪目标数组a、左子数组l和右子数组r的当前位置。它在l和r都有元素时，不断比较两数组当前元素，将较小的一个放入a中，并移动相应数组的指针。当其中一个子数组耗尽后，将另一个子数组中剩余的所有元素直接复制到a的末尾。
5. 三路归并函数实现
除了标准的二路归并，有时我们可能需要将三个或更多已排序的数组合并。实现一个三路归并函数比二路归并稍微复杂，但核心思想是相同的：每次从所有可用数组中选择最小的元素。
为了简化逻辑，我们可以引入一个“哨兵值”Integer.MAX_VALUE来表示一个数组已耗尽，这样就无需复杂的边界条件判断。
public class MergeSort {
// ... (previous methods: main, mergeSort, copyArray, merge) ...
/**
* 三路归并函数，将三个已排序的数组arr1, arr2, arr3合并成一个大的有序数组。
*
* @param arr1 第一个已排序的数组
* @param arr2 第二个已排序的数组
* @param arr3 第三个已排序的数组
* @return 合并后的有序数组
*/
public static int[] mergeArrays3(int[] arr1, int[] arr2, int[] arr3) {
// 创建一个足够大的结果数组来容纳所有元素
int[] result = new int[arr1.length + arr2.length + arr3.length];
// 初始化三个数组的指针和结果数组的指针
int p1 = 0, p2 = 0, p3 = 0, k = 0;
// 循环直到所有数组的元素都被处理完毕
while (p1 < arr1.length || p2 < arr2.length || p3 < arr3.length) {
// 获取当前指针指向的元素值，如果数组已耗尽，则使用Integer.MAX_VALUE作为 
