class Solution {
    /**
     * 归并排序
     * @param A
     */
    public void sortIntegers(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        // 用于合并数组的额外空间
        int mergeArray[] = new int[A.length];
        // 递归调用排序算法
        mergeSort(A, 0, A.length - 1, mergeArray);
    }
    // 将 array 数组中 start 到 end 之间的元素进行排序
    private void mergeSort(int[] array, int start, int end, int[] mergeArray) {
        if (start >= end) {
            // start 如果等于 end, 说明就一个元素, 不用排序
            // start 正常情况下不会大于 end
            return;
        }
        // 先在中间切一刀, 左侧右侧进行分别排序
        // 左侧排序
        mergeSort(array, start, (start + end) / 2, mergeArray);
        // 右侧排序
        mergeSort(array, (start + end) / 2 + 1, end, mergeArray);
        // 进行归并操作, 将已经排好序的两侧的数组进行合并
        merge(array, start, end, mergeArray);
    }
    // 合并两个已经排好序的数组
    private void merge(int[] array, int start, int end, int[] mergeArray) {
        // 左右两个数组的遍历索引, 初值值为左右两侧的开始索引
        int leftIndex = start;
        int rightIndex = (start + end) / 2 + 1;
        // 记录 mergeArray 的赋值索引
        int mergeIndex = leftIndex;
        while (leftIndex <= (start + end) / 2 && rightIndex <= end) {
            if (array[leftIndex] < array[rightIndex]){
                // 先赋值, 然后索引自增
                mergeArray[mergeIndex++] = array[leftIndex++];
            } else {
                mergeArray[mergeIndex++] = array[rightIndex++];
            }
        }
        // 上述赋值完毕后, 可能有一侧还有若干元素没有赋值完毕
        // 检查左侧是否赋值完毕, 如果没有赋值完毕, 则继续遍历, 如果赋值完毕, 则不会进入循环
        while (leftIndex <= (start + end) / 2) {
            mergeArray[mergeIndex++] = array[leftIndex++];
        }
        // 检查右侧是否赋值完毕, 如果没有赋值完毕, 则继续遍历, 如果赋值完毕, 则不会进入循环
        while (rightIndex <= end) {
            mergeArray[mergeIndex++] = array[rightIndex++];
        }
        // 上述操作将排序号的元素都放在 mergeArray 数组中, 在将其设置到 array 数组中
        for (int i = start; i <= end; i++) {
            array[i] = mergeArray[i];
        }
    }
}