Through this post, I’m sharing Python code implementing the median of medians algorithm, an algorithm that resembles quickselect, differing only in the way in which the pivot is chosen, i.e, deterministically, instead of at random.
Its best case complexity is O(n) and worst case complexity O(nlog2n)
I don’t have a formal education in CS, and came across this algorithm while going through Tim Roughgarden’s Coursera MOOC on the design and analysis of algorithms. A video covering that algorithm is shown below, followed by my implementation in Python.
I get the following output:
51 100 loops, best of 3: 2.38 ms per loop
Note that on the same input, quickselect is faster, giving us:
1000 loops, best of 3: 254 µs per loop