Algorithm to find k elements following the median in sorted order
Answering your second question:


Find the median $m$, and partition the set into $L_1 = \{x | x \in S \wedge x &lt; m\}$ and $L_2 = \{x | x \in S \wedge x &gt; m\}$.
Find the $k$th largest element $x_k$ in $L_2$, and partition the set into $L_2' = \{x | x \in L_2  \wedge x \leq x_k\}$ and $L_3 = \{x | x \in L_2 \wedge x &gt; x_k\}$.
Sort $L_2'$ and return.


Steps 1 and 2 take $O(n)$. Step 3 takes $O(k \log k)$. Total time $O(n + k \log k)$.

Note this assumes distinct values. Repeated values involves some edge case handling.