Median

There are quite a few

How to find median of unsorted array in O(n) time? (i.e. without sorting)

• Came up in this problem https://codeforces.com/contest/1993/problem/D

I think we saw it in CS240, through Quickselect, we can do O(n), but worst case is O(n^2)?