Merge Sort

Analysis:

First divide the array (red) until reaches single number. Then starting merge(green). Need a temp array to store the sorted elements while merging. 

Solution:

If start  == end, then the first mergeSort， start to mid, will fell into infinite recursive call. 

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
 public void sortIntegers2(int[] A) {
    // write your code here
    mergeSort(A, new int[A.length], 0, A.length - 1);
}


private void mergeSort(int[] A, int[] temp, int start, int end) {
     if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(A, temp, start, mid);
        mergeSort(A, temp, mid + 1, end);
        merge(A, temp, start, end, mid);
     
}

private void merge(int[] A, int[] temp, int start, int end, int mid) {
    int p1 = start, p2 = mid + 1, p = start;
    // start as point in merged array.
    while (p1 <= mid && p2 <= end) {
        if (A[p1] < A[p2]) {
            temp[p++] = A[p1++];
        } else {
            temp[p++] = A[p2++];
        }
    }
    
    while (p1 <= mid) 
        temp[p++] = A[p1++];
    

    while (p2 <= end)
        temp[p++] = A[p2++];

    for (int i = start; i <= end; i++) 
        A[i] = temp[i];
}
}