Sort Integers II(lintcode 464)

Description

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].

Interface

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
    }
}

Solution

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */

    //Merge Sort
    public void sortIntegers2(int[] A) {
        // Write your code here
        int[] temp = new int[A.length];
        mergeSortHelper(A, temp, 0, A.length - 1);
    }

    private void mergeSortHelper(int[] A, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }

        int middle = left + (right - left) / 2;
        mergeSortHelper(A, temp, left, middle);
        mergeSortHelper(A, temp, middle + 1, right);
        merge(A, temp, left, middle, right);
    }

    private void merge(int[] A, int[] temp, int left, int middle, int right) {
        if (left >= right) {
            return;
        }

        int i = left, j = middle + 1;
        int index = 0;

        while (i <= middle && j <= right) {
            if (A[i] < A[j]) {
                temp[index++] = A[i++];
            } else {
                temp[index++] = A[j++];
            }
        }

        while (i <= middle) {
            temp[index++] = A[i++];
        }

        while (j <= right) {
            temp[index++] = A[j++];
        }

        for (int k = 0; k < right - left + 1; ++k) {
            A[left + k] = temp[k];
        }
    }


    //Quick Sort
    public void sortIntegers2(int[] A) {
        // Write your code here
        quickSortHelper(A, 0, A.length - 1);
    }

    private void quickSortHelper(int[] A, int left, int right) {
        if (left >= right) {
            return;
        }

        int i = left, j = right;
        int pivot = A[left + (right - left) / 2];

        while (i <= j) {
            while (i <= j && A[i] < pivot) {
                ++i;
            }

            while (i <= j && A[j] > pivot) {
                --j;
            }

            if (i <= j) {
                swap(A, i++, j--);
            }
        }

        quickSortHelper(A, left, j);
        quickSortHelper(A, i, right);
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}