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

    void quickSort(int[] nums, int l, int r){
        if(l < r){
            int m = partation(nums, l , r);
            quickSort(nums, l, m-1);
            quickSort(nums, m+1, r);
        }
    }

    int partation(int[] nums, int l, int r){
        int c = nums[r];
        int k = l;
        for(int i =l;i <r; i++){
            if(nums[i] < c){
                swap(nums, i, k);
                k++;
            }
        }
        swap(nums, r, k);
        return k;
    }

    void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

/**
 * 合并两个有序数列
 * array[first]~array[mid]为第一组
 * array[mid+1]~array[last]为第二组
 * temp[]为存放两组比较结果的临时数组
 */
private static void mergeArray(int array[], int first, int mid, int last, int temp[]) {
    int i = first, j = mid + 1; // i为第一组的起点, j为第二组的起点
    int m = mid, n = last; // m为第一组的终点, n为第二组的终点
    int k = 0; // k用于指向temp数组当前放到哪个位置
    while (i <= m && j <= n) { // 将两个有序序列循环比较, 填入数组temp
        if (array[i] <= array[j])
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }
    while (i <= m) { // 如果比较完毕, 第一组还有数剩下, 则全部填入temp
        temp[k++] = array[i++];
    }
    while (j <= n) {// 如果比较完毕, 第二组还有数剩下, 则全部填入temp
        temp[k++] = array[j++];
    }
    for (i = 0; i < k; i++) {// 将排好序的数填回到array数组的对应位置
        array[first + i] = temp[i];
    }
}