Complexity

O(nlog(n)), space O(n)

模板

public void mergeSort(int[] A) {
    int[] temp = new int[A.length];
    partition(A, 0, A.length - 1, temp);
}

public void partition(int[] A, int start, int end, int[] temp) {
    if (start >= end) {
        return;
    }

    int mid = (start + end) / 2;
    partition(A, start, mid, temp);
    partition(A, mid + 1, end, temp);
    merge(A, start, mid, end, temp);
}

public void merge(int[] A, int start, int mid, int end, int[] temp) {
    int left = start;
    int right = mid;
    int index = start;

    // merge two sorted array into temp
    while (left <= mid && right <= end) {
        if (A[left] < A[right]) {
            temp[index++] = A[left++];
        } else {
            temp[index++] = A[right++];
        }
    }
    while (left <= mid) {
        temp[index++] = A[left++];
    }
    while (right <= end) {
        temp[index++] = B[right++];
    }

    // copy temp back to A
    for (index = start; index <= end; index++) {
        A[index] = temp[index];
    }
}

in place- two pointer and swap