def partition(a, lo, hi):
    i, j, v = lo+1, hi, a[lo]
    while(True):
        while(a[i] < v):
            i += 1
            if (i == hi): break
        while(a[j] > v):
            j -= 1
            if (j == lo): break
        if (i >= j): break
        a[i], a[j] = a[j], a[i]
    a[lo], a[j] = a[j], a[lo]
    return j

def sort(a, lo, hi):
    if (hi <= lo):
        return
    q = partition(a, lo, hi)
    sort(a, lo, q-1)
    sort(a, q+1, hi)
    assert isSorted(a, lo, hi)

def quick_sort(a):
    shuffle(a)
    sort(a, 0, len(a)-1)
    assert isSortedArray(a)