Best sort method for median: median heap or insertion sort on a vector
You are asking many questions, and I will only answer two of them. If you have a sorted vector of length $n$ followed by $m$ unsorted elements, the best way to sort the entire vector is to use an $O(m\log m)$ sorting algorithm on the tail, and then merge the two sorted lists in $O(n+m)$. The total running time is $O(n+m\log m)$, which is $O(n)$ if $m = O(n/\log n)$. If $m = \omega(n/\log n)$ then the problem is more complicated; asymptotically optimal bounds are known in the decision tree model, but I'm not sure they can be implemented efficiently enough (see for example Kahn ad Kim, Entropy and Sorting).

Another question, which you haven't actually asked, is about lower bounds. Suppose that you have a data structure in which insert takes (amortized) time $\alpha(n)$ and median takes (amortized) time $\beta(n)$, where $n$ is the number of elements in the structure. Suppose further that $\alpha(O(n)) = O(\alpha(n))$ and $\beta(O(n)) = O(\beta(n))$, and that $\alpha,\beta$ are monotone (this is the case for functions of the type $\Theta(n^s\log^t n)$). Then $\alpha(n) + \beta(n) = \Omega(\log n)$, assuming the operations are implemented using the comparison model (two datums can be compared, but are otherwise completely opaque).

For the proof, here is how to sort a list of length $n$. First insert the list. Then, extract the median, add $-\infty$ (or the minimum value) twice, and repeat. You recover the sorted lower half of the list. Now add enough copies of $+\infty$ (or the maximum value), and recover similarly the upper half of the list. This requires at most $O(n\alpha(O(n)) + n\beta(O(n))) = O(n(\alpha(n)+\beta(n)))$. In the comparison model, there is a lower bound of $\Omega(n\log n)$, so $\alpha(n) + \beta(n) = \Omega(\log n)$.