import random

def quick_sort(nums):
    def sort(left, right):
        if right - left <= 1:
            return
        chosen = random.randrange(left, right)
        nums[chosen], nums[right - 1] = nums[right - 1], nums[chosen]
        pivot = nums[right - 1]
        write = left
        for i in range(left, right - 1):
            if nums[i] <= pivot:
                nums[write], nums[i] = nums[i], nums[write]
                write += 1
        nums[write], nums[right - 1] = nums[right - 1], nums[write]
        sort(left, write)
        sort(write + 1, right)
    sort(0, len(nums))
    return nums