class Solution {
    public int[] sortArray(int[] nums) {
    
        // sort array using quicksort
        sort(nums, 0, nums.length - 1);
        
        return nums;
    }
    
    public void sort(int[] nums, int low, int high) {
        // select index to partition array
        if(low < high) {
            int pi = partition(nums, low, high);

            sort(nums, low, pi-1);
            sort(nums, pi+1, high);
        }
    }

    // partitiion an array by selecting a pivot 
    private int partition(int[] nums, int low, int high) {
        // get random index as the pivot
        int pivot = low + (int) (Math.random() * (high - low) + 1);
        int i = low;
        int j = high;
        
        while(i <= j) {
            if(nums[i] < nums[pivot]) {
                i++;
            }else if(nums[j] >= nums[pivot]) {
                j--;
            } else {
                swap(nums, i, j); // swapping elements out of place 
                i++;
                j--;
            }
        }
        
        swap(nums, pivot, i); // places pivot in the correct position
        return i;
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}