归并排序的核心思想是分治，传统实现多采用二路归并，将数组拆分为两个子数组递归排序后合并。但在处理大规模数据或者需要适配特定分片规则的场景下，自定义数组切片结合多路归并可以更灵活地满足需求，本文将详细介绍Java中实现该策略的完整方法。
核心思路说明
整个实现过程分为三个核心步骤：首先是自定义数组切片，根据设定的切片大小或者规则，将原始无序数组拆分为多个子数组，对每个子数组单独进行排序；然后是多路归并准备，将所有排好序的子数组作为归并的输入源；最后是执行多路归并，每次从所有子数组的当前头部元素中选取最小的，放入结果数组，直到所有子数组的元素都被取完。
自定义数组切片实现
我们首先实现自定义切片逻辑，这里支持两种切片模式，一种是按固定长度切片，另一种是按指定切分点切片，代码如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MergeSortDemo {
// 按固定长度切片，返回切片后的子数组列表
private static List<int[]> sliceArrayByLength(int[] arr, int sliceLength) {
List<int[]> sliceList = new ArrayList<>();
if (arr == null || arr.length == 0) {
return sliceList;
}
int start = 0;
while (start < arr.length) {
int end = Math.min(start + sliceLength, arr.length);
int[] slice = Arrays.copyOfRange(arr, start, end);
// 对每个子数组先进行排序
Arrays.sort(slice);
sliceList.add(slice);
start = end;
}
return sliceList;
}
// 按指定切分点切片，切分点数组存放每个切片的结束索引（不包含）
private static List<int[]> sliceArrayByPoints(int[] arr, int[] splitPoints) {
List<int[]> sliceList = new ArrayList<>();
if (arr == null || arr.length == 0) {
return sliceList;
}
int start = 0;
for (int end : splitPoints) {
if (end <= start || end > arr.length) {
continue;
}
int[] slice = Arrays.copyOfRange(arr, start, end);
Arrays.sort(slice);
sliceList.add(slice);
start = end;
}
// 处理最后一个切片
if (start < arr.length) {
int[] lastSlice = Arrays.copyOfRange(arr, start, arr.length);
Arrays.sort(lastSlice);
sliceList.add(lastSlice);
}
return sliceList;
}
}
多路归并实现逻辑
多路归并需要同时维护多个子数组的当前遍历位置，每次选取最小值后更新对应子数组的指针，实现代码如下：
import java.util.PriorityQueue;
public class MergeSortDemo {
// 多路归并方法，输入排好序的子数组列表，返回合并后的完整有序数组
private static int[] multiWayMerge(List<int[]> sortedSlices) {
if (sortedSlices == null || sortedSlices.isEmpty()) {
return new int[0];
}
// 优先队列存储每个子数组的当前元素和对应的数组索引、元素索引
PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.value - b.value);
// 初始化优先队列，加入每个子数组的第一个元素
for (int i = 0; i < sortedSlices.size(); i++) {
int[] slice = sortedSlices.get(i);
if (slice.length > 0) {
queue.add(new Node(slice[0], i, 0));
}
}
int totalLength = sortedSlices.stream().mapToInt(arr -> arr.length).sum();
int[] result = new int[totalLength];
int index = 0;
while (!queue.isEmpty()) {
Node current = queue.poll();
result[index++] = current.value;
int nextIdx = current.elementIdx + 1;
int[] currentSlice = sortedSlices.get(current.sliceIdx);
if (nextIdx < currentSlice.length) {
queue.add(new Node(currentSlice[nextIdx], current.sliceIdx, nextIdx));
}
}
return result;
}
// 内部节点类，记录当前元素值、所属子数组索引、元素在子数组中的索引
static class Node {
int value;
int sliceIdx;
int elementIdx;
Node(int value, int sliceIdx, int elementIdx) {
this.value = value;
this.sliceIdx = sliceIdx;
this.elementIdx = elementIdx;
}
}
}
完整调用示例
我们将切片和归并逻辑组合起来，完成整个排序流程，示例如下：
public class MergeSortDemo {
public static void main(String[] args) {
int[] originalArray = {5, 2, 7, 1, 9, 3, 8, 4, 6};
// 按固定长度3切片
List<int[]> slices = sliceArrayByLength(originalArray, 3);
System.out.println("切片后的子数组：");
for (int[] slice : slices) {
System.out.println(Arrays.toString(slice));
}
// 多路归并
int[] sortedArray = multiWayMerge(slices);
System.out.println("最终排序结果：" + Arrays.toString(sortedArray));
}
}
复杂度分析
假设原始数组长度为n，切片后共有k个子数组，每个子数组平均长度为m，满足n = k * m。切片阶段对每个子数组排序的时间复杂度为O(k * m log m) = O(n log m)，多路归并阶段使用优先队列，每次操作时间复杂度为O(log k)，总共有n个元素，因此归并阶段时间复杂度为O(n log k)，整体时间复杂度接近O(n log n)。空间复杂度方面，需要存储切片数组和优先队列，整体为O(n)。
注意事项
- 自定义切片时需要注意切分点的合法性，避免出现索引越界的问题
- 多路归并的优先队列初始容量可以设置为子数组的数量，减少扩容开销
- 如果子数组已经有序，可以跳过子数组的排序步骤，直接进行归并，提升效率