归并排序-Java实现

在极客时间学习时，又遇到了归并排序，这里给出Java的实现，附有注解，以备后面学习查看

private int[] sortArray(int[] waitDealArray) {
    if(waitDealArray == null) {
        return new int[0];
    }
    if(waitDealArray.length == 1) {
        return waitDealArray;
    }
    int middleIdx = waitDealArray.length / 2;
    // 将数组从中间分成左右两个，分而治之
    int[] leftArray = Arrays.copyOfRange(waitDealArray, 0, middleIdx);
    int[] rightArray = Arrays.copyOfRange(waitDealArray, middleIdx, waitDealArray.length);
    // 递归调用处理子问题
    leftArray = sortArray(leftArray);
    rightArray = sortArray(rightArray);
    // 合并子问题处理的结果
    int[] mergedArray = mergeArray(leftArray, rightArray);
    return mergedArray;
}

private int[] mergeArray(int[] leftArray, int[] rightArray) {
    if(leftArray == null) {
        leftArray = new int[0];
    }
    if(rightArray == null) {
        rightArray = new int[0];
    }
    int[] mergedArray = new int[leftArray.length + rightArray.length];
    int mi = 0, li = 0, ri = 0;
    // 用来合并两个有序数组内的数字
    while(li < leftArray.length && ri < rightArray.length) {
        if(leftArray[li] <= rightArray[ri]) {
            mergedArray[mi] = leftArray[li];
            li++;
        } else {
            mergedArray[mi] = rightArray[ri];
            ri++;
        }
        mi++;
    }
    // 如果某个数组还有剩余数字，直接放入合并数组即可
    if(li < leftArray.length) {
        for(int i = li; i < leftArray.length; i++) {
            mergedArray[mi] = leftArray[li];
            mi++;
        }
    }
    if(ri < rightArray.length) {
        for(int i = ri; i < rightArray.length; i++) {
            mergedArray[mi] = rightArray[i];
            mi++;
        }
    }
    return mergedArray;
}

写一个测试用例测试下:

/**
 * 测试归并排序操作
 */
@Test
public void testUnionSort() {
    int[] waitDealArray = {234, 12, 45, 2, 908, 111, 309, 103, 205, 9};
    int[] sortedArray = sortArray(waitDealArray);
    System.out.println(Arrays.toString(sortedArray));
}

打印结果：

[2, 9, 12, 45, 103, 111, 205, 234, 309, 908]