Sort

Quick Sort

    private void quickSort(int[] nums, int start, int end){
        if(start>=end) return;
        int mid = partition(nums, start, end);
        quickSort(nums, start, mid-1);
        quickSort(nums, mid+1, end);
    }
    
    // set the select num in the correct position in nums
    // return the index of the selected num
    private int partition(int[] nums, int start, int end){
        int ran = (int) (Math.random()*(end - start + 1) + start);
        swap(nums, ran, end);
        
        int left = start;
        int right = end-1;
        while(left<=right){
            if(nums[left]>nums[end]){
                swap(nums, left, right);
                right--;
            }else{
                left++;
            }
        }
        // put the pivot to the correct position;
        swap(nums, left, end);
        // index of left now is the index of pivot
        return left;
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

merge sort

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
        return nums;
    }
    
    private void mergeSort(int[] nums, int start, int end){
        if(start>=end) return;
        
        int mid = start+(end-start)/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){
        // copy the two sorted part
        int[] arr = new int[end-start+1];
        for(int i=0; i<arr.length; i++){
            arr[i] = nums[i+start];
        }
        
        int left = 0;
        int right = mid-start+1;
        for(int i=start; i<=end; i++){
            // left out of the boundary
            if(left == mid-start+1){
                nums[i]=arr[right++];
            }else if(right == end-start+1){
                // right out of the boundary
                nums[i]=arr[left++];
            }else{
                nums[i] = arr[left]<=arr[right] ? arr[left++] : arr[right++];
            }
        }
    }
}