各种sort总结

public int[] mergeSort(int[] nums){
        //int[] res = {};
        if(nums == null || nums.length < 2){
            return nums;
        }

        mergeSortHelper(nums, 0, nums.length - 1);

        return nums;
    }

    public void mergeSortHelper(int[] nums, int i, int j){

        if(i >= j) //recursion: 什么时候停止
            return;

        int left = i;
        int right = j;
        int mid = left + (right - left)/2;
        mergeSortHelper(nums, left, mid);
        mergeSortHelper(nums, mid + 1, right);
        merge(nums, left, mid + 1, right);

    }

    public void merge(int[] nums, int start1, int start2, int end){
        int[] res = new int[end - start1 + 1]; //踩坑点！！

        int p1 = start1, p2 = start2;
        int i = 0;
        while(p1 < start2 && p2 <= end){
            if(nums[p1] < nums[p2]){
                res[i] = nums[p1];
                p1++;
            }else{
                res[i] = nums[p2];
                p2++;
            }
            i++;
        }
        //post processing
        while(p1 < start2){
            res[i++] = nums[p1++];
        }

        while(p2 <= end){
            res[i++] = nums[p2++];
        }

        for(int num: res){
            nums[start1++] = num;
        }
    }