3 * n/2 - 2 comparisons, tournament method

tournament.py

x = [1, 5, 3, 9, 10, 6, 0, 11, 21, -10, 5]

small, large = x[0], x[0]

for i in range(1, len(x) - 1):
    if x[i] < x[i + 1]:
        small = min(x[i], small)
        large = max(x[i + 1], large)
print(small, large)

# 3 * n/2 - 2 comparisons, tournament method

"""
If odd, set both to same value like above.

If even, perform one manual comparison to determine the min and max at the start. 

if n is odd, we do 3[n/2] comparisons.

if n is even, we perform 1 initial comparison followed by 3(n - 2)/2 for a total of 3n(2 - 2).

The total compairsons at most is 3[n/2]

"""