-1

Suppose we have mysterious machine which return median $m$ of given set $S$ and set $S/\{m\}$ in constant time, where $S/\{m\}$ denotes the difference of $S$ and element $m$. Prove that we can sort any list of $n$ elements in linear time using such machine. (extra space is allowed)
Here is my ide...