public class MergeSort {
// 归并排序
public static void mergeSort(int[] numArray) {
// 执行归并排序
_mergeSort(numArray, 0, numArray.length - 1);
}
// 对指定起始位置和终了位置的数组执行归并排序
private static void _mergeSort(int[] numArray, int startIndex, int endIndex) {
// 如果数组长度为1，则不需要再分
if (startIndex == endIndex) {
return;
}
// 将数组平分为两个数组
int centIndex = (startIndex + endIndex) / 2;
// 分别将两个数组排序
_mergeSort(numArray, startIndex, centIndex);
_mergeSort(numArray, centIndex + 1, endIndex);
// 将排序后的两个数组合并为一个
_mergeArray(numArray,startIndex, centIndex, endIndex);
}
// 将两个数组合并为一个
private static void _mergeArray(int[] numArray, int startIndex, int centIndex, int endIndex) {
// 创建存放排序结果的临时数组
int[] rstArray = new int[endIndex - startIndex + 1];
// 从两个数组头部开始，依次挑出较小的元素，放入结果数组中
int rstIndex = 0;
int leftIndex = startIndex;
int rightIndex = centIndex + 1;
while (true) {
// 如果左边数组头部较小
if (numArray[leftIndex] <= numArray[rightIndex]) {
// 将左边数组头部元素放入结果数组
rstArray[rstIndex] = numArray[leftIndex];
// 将结果数组当前索引加1
rstIndex++;
// 将左数组索引指向下一个元素
leftIndex++;
// 如果左数组已空，则把右数组剩余的内容复制到结果数组中，排序完毕
if (leftIndex > centIndex) {
// 拷贝数组
_copyArray(numArray, rightIndex, endIndex, rstArray, rstIndex);
// 排序完毕，退出循环
break;
}
// 如果右边数组头部较小
} else {
// 将右边数组头部元素放入结果数组
rstArray[rstIndex] = numArray[rightIndex];
// 将结果数组当前索引加1
rstIndex++;
// 将右数组索引指向下一个元素
rightIndex++;
// 如果右数组已空，则把左数组剩余的内容复制到结果数组中，排序完毕
if (rightIndex > endIndex) {
// 拷贝数组
_copyArray(numArray, leftIndex, centIndex, rstArray, rstIndex);
// 排序完毕，退出循环
break;
}
}
}
// 将排序后的结果放回原数组
_copyArray(rstArray, 0, rstArray.length - 1, numArray, startIndex);
}
// 拷贝数组
private static void _copyArray(int[] srcArray, int srcStartIndex, int srcEndIndex,
int[] rstArray, int rstStartIndex) {
// 计算拷贝长度
int length = srcEndIndex - srcStartIndex + 1;
for (int i = 0; i < length; i++) {
rstArray[rstStartIndex + i] = srcArray[srcStartIndex + i];
}
}
}