quicksort.py

counts = 0


def quicksort(arr):
    global counts
    if len(arr) >= 1:
        counts += len(arr)-1
    if len(arr) <= 1:
        return arr
    else:
        # Median of three lol
        indexes = sorted([(0, arr[0]), (-1, arr[-1]), ((len(arr)-1)//2, arr[(len(arr)-1)//2])], key=lambda x: x[1])
        index, _ = indexes[1]
        m = arr[index]
        arr[index] = arr[0]
        arr[0] = m
        pivot = arr[0]
        i = 1
        for j in xrange(1, len(arr)):
            if arr[j] < pivot:
                m = arr[j]
                arr[j] = arr[i]
                arr[i] = m
                i += 1
        arr[0] = arr[i-1]
        arr[i-1] = pivot
        arr[:i-1] = quicksort(arr[:i-1])
        arr[i:] = quicksort(arr[i:])
        return arr


if __name__ == '__main__':
    # Load file into readable integer array
    with open('array.txt') as f:
        data = f.readlines()
    data = [int(num.rstrip()) for num in data]
    # Check implementation
    assert quicksort(data) == sorted(data)
    print counts
    # Answers:
    # 1. 162085
    # 2. 164123
    # 3. 138382