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(nlog_{2}n)

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. Check out 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

### Like this:

Like Loading...

You use middle_index on line 49 & 53. Is this from some library or import? Is it a custom function?

Thank you

LikeLike