import datetime


comparisons = 0

def partition(A, left, right):
    global comparisons
    length = right + 1 - left
    middle = int(length / 2) - 1 if not length % 2 else int(length / 2)
    middle = left + middle  # shift

    # find median index
    x = sorted([A[left], A[middle], A[right]])[1]
    for v, i in [(A[left], left), (A[middle], middle), (A[right], right)]:
        if x == v:
            median = i
            break

    pivot = A[median]

    A[left], A[median] = A[median], 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):
    global comparisons
    if p < r:
        q = partition(A, p, r)
        # comparisons += q - 1 - p
        qsort(A, p, q - 1)
        # comparisons += r - q + 1
        qsort(A, q + 1, r)


if __name__ == '__main__':
    A = []
    # with open('QuickSort.txt') as f:
    with open('IntegerArray.txt') as f:
        for line in f:
            A.append(int(line))

    time = datetime.datetime.now()
    qsort(A, 0, len(A) - 1)
    time = datetime.datetime.now() - time
    assert A == sorted(A)
    print(comparisons, time) # 1697653 0:00:00.600502
