Finding the second largest element in a list with n + log2(n) - 2 comparisions

second.py

from collections import defaultdict
from random import shuffle


def compare(a, b):
    return (a, b) if a > b else (b, a)


def second_largest(nums):

    # Store all the results of the comparisions
    loser_dict = defaultdict(list)
    

    def largest(nums):
        if len(nums) == 2:
            [a, b] = nums
            return compare(a, b)

        # This assumes the array length is a power of 2.
        # If it isn't then we should pad it
        mid = int(len(nums) / 2)

        left = nums[:mid]
        right = nums[mid:]

        left_winner, left_loser = largest(left)
        loser_dict[left_winner].append(left_loser)

        right_winner, right_loser = largest(right)
        loser_dict[right_winner].append(right_loser)

        total_winner, total_loser = compare(left_winner, right_winner)
        loser_dict[total_winner].append(total_loser)
        return (total_winner, total_loser)

    # Finding the largest element takes n comparisons
    biggest, _ = largest(nums)
    
    # There will be log2(n) - 1 losers
    # To find the largest number you need k - 1 comparisons
    # So this takes log2(n) - 2 comparisons
    return max(loser_dict[biggest])


nums = list(range(2**16))
shuffle(nums)

print(second_largest(nums))