Cacher is the code snippet organizer for pro developers

/*
时空复杂度：

*/
public class Solution {
    public int[] mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        return mergeSort(array, 0, array.length - 1);
    }

    private int[] mergeSort(int[] array, int left, int right) {
        // base case
        // new一个array去返回因为这里使用了挡板法的虚拟思想 当left == right的时候这个array只剩一个元素
        // 并不代表这个array传入的时候只有一个元素
        if (left == right) {
            return new int[] { array[left] };
        }
        int mid = left + (right - left) / 2;
        int[] leftResult = mergeSort(array, left, mid);
        int[] rightResult = mergeSort(array, mid + 1, right);
        return merge(leftResult, rightResult);
    }

    private int[] merge(int[] leftResult, int[] rightResult) {
        int[] result = new int[leftResult.length + rightResult.length];
        int p1 = 0, p2 = 0, p3 = 0;
        while (p1 < leftResult.length && p2 < rightResult.length) {
            if (leftResult[p1] < rightResult[p2]) {
                result[p3] = leftResult[p1];
                p1++;
                p3++;
            } else {
                result[p3] = rightResult[p2];
                p2++;
                p3++;
            }
        }
        while (p1 < leftResult.length) {
            result[p3] = leftResult[p1];
            p1++;
            p3++;
        }
        while (p2 < rightResult.length) {
            result[p3] = rightResult[p2];
            p2++;
            p3++;
        }
        return result;

    }

}