Sort Integers II

• Merge sort

Java

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // use a shared temp array, the extra memory is O(n) at least
        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, mid, end, temp);
    }
    
    private void merge(int[] A, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid+1;
        int index = start;
        
        // merge two sorted subarrays in A to temp array
        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++];
        }
        
        // copy temp back to A
        for (index = start; index <= end; index++) {
            A[index] = temp[index];
        }
    }
}

• Quick sort

Java

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
    public void sortIntegers2(int[] A) {
        // write your code here
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = partition(A, start, end);
        quickSort(A, start, mid - 1);
        quickSort(A, mid + 1, end);
    }
    
    private int partition(int[] A, int start, int end) {
        int pivot = A[start];
        int i = start + 1;
        int j = end;
        while (i <= j) {
            while (i <= j && A[i] <= pivot) {
                i++;
            }
            while (i <= j && A[j] > pivot) {
                j--;
            }
            if (i > j) {
                break;
            } 
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            j--;
            i++;
        }
        A[start] = A[j];
        A[j] = pivot;
        return j;
    }
}

• Heap sort

Java

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
    public void sortIntegers2(int[] A) {
        // write your code here
        if (A.length < 2) {
            return;
        }
        for (int i = A.length / 2; i >= 0; i--) {
            reHeap(A, i, A.length - 1);
        }
        int temp = A[0];
        A[0] = A[A.length - 1];
        A[A.length - 1] = temp;
        for (int i = A.length - 2; i > 0; i--) {
            reHeap(A, 0, i);
            temp = A[0];
            A[0] = A[i];
            A[i] = temp;
        }
    }
    
    private void reHeap(int[] A, int start, int end) {
        int val = A[start];
        for (int i = 2 * start + 1; i <= end; start = i, i = 2 * start + 1) {
            if (i < end && A[i + 1] > A[i]) {
                i++;
            }
            if (val >= A[i]) {
                break;
            }
            A[start] = A[i];
        }
        A[start] = val;
    }
}