class Solution {
    public int[] sortArray(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        quickSort(nums, low, high);
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    void quickSort(int [] a, int low, int high){
        if(low >= high) return;
        int left = low;
        int right = high;
        int pivot = a[(left + right) / 2];
        while(left <= right){
            while(left <= right && a[left] < pivot){
                left ++;
            }
            while(left <= right && a[right] > pivot){
                right--;
            }
            if(left <= right){
                int temp = a[left];
                a[left] = a[right];
                a[right] = temp;
                left ++;
                right --;
            }
        }
        quickSort(a, low, right);
        quickSort(a, left, high);
    }
    
    void bubbueSort(int [] nums){
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < nums.length - 1 -i; j++){
                if(nums[j] > nums[j + 1]){
                    int temp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }
    void insertionSort(int [] nums){
        for(int end = 1; end < nums.length; end++){
            int curr = end;
            while(curr - 1 >= 0 && nums[curr - 1]  > nums[curr]){
                int temp = nums[curr - 1];
                nums[curr - 1] = nums[curr];
                nums[curr] = temp;
                curr --;
            }
        }
    }
    void selectionSort(int [] nums){
        for(int i = 0; i < nums.length; i++){
            int minIndex = i;
            for(int j = i + 1; j < nums.length; j++){
                minIndex = nums[j] < nums[minIndex] ? j : minIndex;
            }
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
    }
    void mergeSort(int [] nums, int left, int right){
        if(left == right) return;
        int mid = left + ((right - left) >> 1);
        mergeSort(nums,left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    void merge (int [] nums, int left, int mid , int right){
        int [] help = new int [right - left + 1];
        int p1 = left;
        int p2 = mid + 1;
        int i = 0 ;
        while(p1<= mid && p2 <= right ){
            help[i++] = nums[p1] < nums[p2]? nums[p1++] : nums[p2++];
        }
        while(p1 <= mid){
             help[i++] = nums[p1 ++];
        }
        while(p2 <= right){
             help[i++] = nums[p2 ++];
        }
        for(int j = 0; j < help.length; j++){
            nums[left + j ] = help [j];
        }
    }

}