Sort Integers II

Sort Integers II

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

mergesort

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        mergeSort(A, 0, A.length - 1);
    }
    
    private void mergeSort(int[] A, int left, int right) {
        if (left >= right) {
            return;
        }
        
        int middle = left + (right - left) / 2;
        mergeSort(A, left, middle);
        mergeSort(A, middle + 1, right);
        
        merge(A, left, middle, right);
    }
    
    private void merge(int[] A, int left, int middle, int right) {
        int i = left;
        int j = middle + 1;
        int k;
        
        int[] temp = new int[right - left + 1];
        for (k = 0; k < right - left + 1; k++) {
            if (i <= middle &&(j > right || A[j] >= A[i])) {
                temp[k] = A[i];
                i++;
            }
            else {
                temp[k] = A[j];
                j++;
            }
        }
        
        for (k = 0; k < right - left + 1; k++) {
            A[left + k] = temp[k];
        }
    }
}

QuickSort with 3-way partition

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        
        int lo = 0;
        int hi = A.length - 1;
        quickSort(A, lo, hi);
        
    }
    
    public void quickSort(int[] A, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        
        int v = A[lo];
        int lt = lo;
        int gt = hi;
        int i = lo + 1;
        
        while (i <= gt) {
            if (A[i] < v) {
                exch(A, lt++, i++);
            }
            else if (A[i] > v) {
                exch(A, i, gt--);
            }
            else {
                i++;
            }
        }
        quickSort(A, lo, lt - 1);
        quickSort(A, gt + 1, hi);
    }
    
    public void exch(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}