归并排序的核心思想是分治，先将数组拆分为左右两个子数组分别排序，再将排好序的子数组合并为完整的有序数组。这个过程中子数组的索引范围计算如果不够严谨，就会触发数组越界异常。
子数组范围越界的常见根源
中间索引计算错误
很多开发者在计算左右子数组的拆分点时，会直接使用int mid = (left + right) / 2的方式，当left和right都是较大的正整数时，两者相加可能会超过int类型的最大值，导致计算结果溢出，得到的mid值超出数组合法索引范围，后续操作子数组时就会越界。
合并阶段的循环边界错误
合并两个有序子数组时，需要分别定义左右子数组的指针，当其中一个子数组的元素全部合并完成后，需要将另一个子数组的剩余元素拷贝到结果数组中。如果剩余元素拷贝的循环边界设置错误，比如指针超过了子数组的实际长度，就会触发越界。
递归终止条件设置不当
归并排序的递归终止条件通常是左边界大于等于右边界，如果错误设置为左边界大于右边界，当子数组只有一个元素时不会终止递归，继续拆分就会得到不合法的索引范围，最终导致越界。
正确的归并排序实现
无溢出的中间索引计算
计算中间索引时，使用int mid = left + (right - left) / 2的方式，避免两个大整数相加溢出的问题，保证mid始终在[left, right]的合法范围内。
完整的实现代码
以下是避免子数组越界的正确归并排序实现：
public class MergeSort {
// 对外暴露的排序方法
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
// 递归拆分并排序
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
// 递归终止条件：子数组只有一个元素
if (left >= right) {
return;
}
// 计算中间索引，避免溢出
int mid = left + (right - left) / 2;
// 排序左子数组
mergeSort(arr, left, mid, temp);
// 排序右子数组
mergeSort(arr, mid + 1, right, temp);
// 合并两个有序子数组
merge(arr, left, mid, right, temp);
}
// 合并两个有序子数组
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 拷贝原数组对应区间的元素到临时数组
System.arraycopy(arr, left, temp, left, right - left + 1);
int i = left;
int j = mid + 1;
int k = left;
// 比较两个子数组的元素，将较小的元素放到原数组对应位置
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
// 将左子数组剩余元素拷贝到原数组
while (i <= mid) {
arr[k++] = temp[i++];
}
// 将右子数组剩余元素拷贝到原数组
while (j <= right) {
arr[k++] = temp[j++];
}
}
// 测试方法
public static void main(String[] args) {
int[] arr = {5, 2, 8, 1, 9, 3};
sort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
实现要点说明
- 中间索引计算使用
left + (right - left) / 2，避免整数溢出导致的索引错误。 - 递归终止条件设置为
left >= right，保证单个元素的子数组不会继续拆分。 - 合并阶段先拷贝原数组区间元素到临时数组，避免合并过程中原数组元素被覆盖，同时循环边界严格控制在子数组的索引范围内。
- 剩余元素拷贝的循环条件明确限定指针不超过子数组的右边界，避免越界访问。