The problem is pretty straightforward. You’re given a number one at a time, and you have to compute the median of the numbers given up to this point.

Naive implementation could be to sort the numbers up to this point and then compute the median. We have to traverse at most $\mathcal{O}(n\log{n})$ elements for each given element as std::sort guarantees sorting in $\mathcal{O}(n\log{n})$ (C++11 and above). So for $n$ elements, the time complexity becomes $\mathcal{O}(n^2\log{n})$.

But this is not the best we can do. We can improve the running time by taking the idea from insertion sort. Remember the invariant of the insertion sort? When we iterate index $i$, the sub-array from $[0 \ldots i - 1]$ is sorted. We have to traverse at most $\mathcal{O}(n)$ elements to find the right position for a given number $n$. So, the running time becomes $\mathcal{O}(n^2)$.

Here’s my implementation in C++: