Hands-On Data Structures and Algorithms with Python - Second Edition

Median of medians

The median_of_medians function is responsible for finding the approximate median of any given list of items. The function uses recursion to return the true median:

def median_of_medians(elems):     sublists = [elems[j:j+5] for j in range(0, len(elems), 5)]     medians = []     for sublist in sublists:         medians.append(sorted(sublist)[len(sublist)//2])     if len(medians) <= 5:         return sorted(medians)[len(medians)//2]     else:         return median_of_medians(medians) 

The function begins by splitting the list, elems, into groups of five elements each. This means that if elems contains 100 items, there will be 20 groups that are created by the sublists = [elems[j:j+5] for j in range(0, len(elems), 5)] statement, with each containing exactly five ...