merge Sort

mergeSort 用的这个temp直接给吧，要不会memory overflow

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
    public void sortIntegers2(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return;
        }
        int[] temp = new int[A.length];
        mergeSort(A, temp, 0, A.length - 1);
    }
    public 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, mid, end);
    }
    public void merge(int[] A,int[] temp, int start, int mid, int end) {
        int left = start;
        int right = mid + 1;

        int index = start;
        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++] = A[right++];
        }
        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
    }
}