comparisons = 0

def partition(A, left, right):
    global comparisons
    pivot = A[left]
    i = left + 1
    for j in range(left + 1, right + 1):  # j = (left, right]
        comparisons += 1
        if A[j] < pivot:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[left], A[i - 1] = A[i - 1], A[left]
    return i - 1  # ?


def qsort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        qsort(A, p, q - 1)
        qsort(A, q + 1, r)

print(comparisons)

if __name__ == '__main__':
    ls = [3, 8, 2, 5, 1, 4, 7, 6]
    qsort(ls, 0, len(ls) - 1)
    print(ls)
