Sorting: HeapSort, RadixSort, MergeSort, QuickSort

Using the LeetCode problem Sort an Array to practice different sorting algorithms.

class Solution {
    public int[] sortArray(int[] nums) {
        // quickSort(nums, 0, nums.length - 1);
        // mergeSort(nums, 0, nums.length - 1);
        // radixSortPosAndNag(nums);
        heapSort(nums);
        return nums;
    }

    /**
      HeapSort.
      39ms, 52.5MB.
     */
     private void heapSort(int[] nums){
         System.out.println("heap: ");
        // Heapify: max heap.
        // Note that we only need to sink non-leaf node.
        for(int i = nums.length / 2; i >= 0; i --) sink(nums, i, nums.length);

        // Sort.
        for(int j = nums.length - 1; j >= 1; j --) {
            swap(nums, j, 0);
            sink(nums, 0, j);
        }
     }

     private void sink(int[] nums, int k, int limit){
         while(2 * k < limit){
            // Already larger than all children.
            int maxChildIndex = 2 * k;
            if(2 * k + 1 < limit && nums[2 * k + 1] > nums[maxChildIndex]) maxChildIndex ++;
            if(nums[k] >= nums[maxChildIndex]) break;

            swap(nums, k, maxChildIndex);
            k = maxChildIndex;
         }
     }

    /**
      RadixSort.
      28ms, 51.9MB.
     */
    private void radixSortPosAndNag(int[] nums){
        int posCount = 0;
        for(int num: nums) {
            if(num >= 0) posCount ++;
        }

        int[] pos = new int[posCount], neg = new int[nums.length - posCount];
        int p = 0, n = 0;
        for(int num: nums) {
            if(num >= 0) pos[p ++] = num;
            else neg[n ++] = num * -1;
        }

        if(pos.length > 0) radixSort(pos);
        if(neg.length > 0) radixSort(neg);

        for(int i = 0; i < neg.length; i ++) nums[i] = neg[neg.length - 1 - i] * -1;
        for(int i = 0; i < pos.length; i ++) nums[neg.length + i] = pos[i];
    }

    private void radixSort(int[] nums) {
        int[] arr = new int[nums.length];
        int exp = 1, max = findMax(nums);

        while(max / exp > 0) {
            int[] radix = new int[10];
            // Put numbers to the radix.
            for(int num: nums) radix[(num / exp) % 10] ++;
            for(int i = 1; i < radix.length; i ++) radix[i] += radix[i - 1];

            // Put numbers back to array.
            for(int i = nums.length - 1; i >= 0; i --) arr[-- radix[(nums[i] / exp) % 10]] = nums[i];
            for(int i = 0; i < nums.length; i ++) nums[i] = arr[i];

            exp *= 10;
        }        
    }

    private int findMax(int[] nums){
        int max = nums[0];
        for(int num: nums) {
            if(num > max) max = num;
        }
        return max;
    }

    /**
       Top-down mergeSort.
       29ms, 53.6MB.
     */
    private void mergeSort(int[] nums, int start, int end){
        if(start >= end) return;

        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    private void merge(int[] nums, int start, int mid, int end) {   
        int[] aux = new int[end - start + 1];
        int i = 0, i1 = start, i2 = mid + 1;
        while(i < aux.length) {
            if(i2 > end) aux[i ++] = nums[i1 ++];
            else if(i1 > mid) aux[i ++] = nums[i2 ++];
            else if(nums[i1] <= nums[i2]) aux[i ++] = nums[i1 ++];
            else aux[i ++] = nums[i2 ++];
        }
        
        for(int j = 0; j < aux.length; j ++) nums[j + start] = aux[j];
    }

    /**
       QuickSort: 3-way partition + randomized pivot. 5 pointers.
       38ms, 51.4MB.
     */
    private void quickSort(int[] nums, int start, int end) {
        if(start >= end) return;

        // Randomize the pivot.
        Random rand = new Random();
        int pivot1 = rand.nextInt(end - start) + start, pivot2 = end, i = start + 1;
        // Move pivot to the start of the array.
        swap(nums, pivot1, start);
        pivot1 = start;
        int pivotValue = nums[start];

        // Partition. [start, pivot1 - 1], [pivot1, pivot2], [pivot2 + 1, end]
        // Note that we need equal condition here.
        while(i <= pivot2) {
            if(nums[i] < pivotValue) swap(nums, i ++, pivot1 ++);
            else if(nums[i] > pivotValue) swap(nums, i, pivot2 --);
            else i ++;
        }
        quickSort(nums, start, pivot1 - 1);
        quickSort(nums, pivot2 + 1, end);
    }  

    /**
        Common helper functions.
     */
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void debug(int[] nums){
        for(int n: nums) System.out.print(n+", ");
        System.out.println();
    }
}