def partition(low, high, arr):
    index = low - 1
    mid = arr[high]
    for i in range(low, high + 1):
        if arr[i] < mid:
            index += 1
            arr[i], arr[index] = arr[index], arr[i]
    index += 1
    arr[index], arr[high] = arr[high], arr[index]
    return index

def quick_sort(low, high, arr):
    if low < high:
        p = partition(low, high, arr)
        quick_sort(low, p - 1, arr)
        quick_sort(p + 1, high, arr)