码农路上

public class Sort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeSort(new int[]{9,8,7,4,6,2,5,3})));
    }

    /**
     * 归并排序
     * @param toSort 待排序的数组
     * @return 排好序的数组
     */
    public static int[] mergeSort(int[] toSort) {
        if (null == toSort) {
            return new int[0];
        }
        if (toSort.length == 1) {//如果只分解到一个元素则直接返回改数
            return toSort;
        }
        //将数组分解左右两半
        int left[] = Arrays.copyOfRange(toSort, 0, toSort.length / 2);
        int right[] = Arrays.copyOfRange(toSort, toSort.length / 2,toSort.length);

        //嵌套调用,对两半分别进行排序
        left = mergeSort(left);
        right = mergeSort(right);

        //合并排好序的两半
        int [] mergeResult = merge(left,right);
        return mergeResult;
    }

    /**
     * 合并两个已经排序完毕的数组(从小到大)
     * @param left 第一个数组
     * @param right  第二个数组
     * @return 合并后的数组
     */
    private static int[] merge(int[] left, int[] right) {
        if (left == null) {
            left = new int[0];
        }
        if (right == null) {
            right = new int[0];
        }
        int result[] = new int[left.length + right.length];
        int leftIndex =0, rightIndex=0, resultIndex=0;
        // 轮流从两个数组中取出较小的值,放入合并后的数组中
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] <= right[rightIndex]) {
                result[resultIndex] = left[leftIndex];
                leftIndex++;
            } else {
                result[resultIndex] = right[rightIndex];
                rightIndex++;
            }
            resultIndex++;
        }

        // 将某个数组中还有剩余的数字,接着放入合并后的新数组中
        if (leftIndex < left.length) {
            for (int i = leftIndex; i < left.length; i++) {
                result[resultIndex] = left[i];
                resultIndex++;
            }

        }
        if (rightIndex < right.length) {
            for (int i = rightIndex; i < right.length; i++) {
                result[resultIndex] = right[i];
                resultIndex++;
            }

        }
        return result;
    }
}