Merge Sort

Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

Example:

Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].

Code:

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return;
        }
        int[] temp = new int[A.length];
        mergeSort(A, 0, A.length - 1, temp);
    }

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

    private void merge(int[] A, int start, int end, int[] temp) {
        int left = start;
        int mid = (start + end) / 2;
        int right = mid + 1;
        int i = start;
        while (left <= mid && right <= end) {
            if (A[left] <= A[right]) {
                temp[i++] = A[left++];
            } else {
                temp[i++] = A[right++];
            }
        }
        while (left <= mid) {
            temp[i++] = A[left++];
        }
        while (right <= end) {
            temp[i++] = A[right++];
        }
        for (int j = start; j <= end; j++) {
            A[j] = temp[j];
        }
    }
}