An algorithm to find second largest element in a list in n + log n - 2 comparisions

tournament.py

# Finding the second best player in a knockout tournament

defeatedListMap = {}

def fillMap(x,y):
        if x in defeatedListMap:
                defeatedListMap[x].add(y)
        else:
                defeatedListMap[x] = set([y])


def largest(array):
        if len(array) == 0:
                return array
        elif len(array) == 1:
                return array[0];
        elif len(array)== 2:
                fillMap(array[0], array[1])
                if(array[0]>array[1]):
                        fillMap(array[0],array[1])
                        return array[0]
                else:
                        fillMap(array[1], array[0])
                        return array[1]
        else:
                x = largest(array[:len(array)/2])
                y = largest(array[len(array)/2:])
                if x > y:
                        fillMap(x,y)
                        return x
                else:
                        fillMap(y,x)
                        return y


# generate a randomize draw for matches
import random
inputList = range(1,17)
random.shuffle(inputList)

#get the champion
champion  =  largest(inputList)

# look for the runner up in the list of players defeatee by champion
runnerUp = largest(list(defeatedListMap.get(champion)))

print champion, runnerUp