Are you sure that's not O(n*log(n))?
It looks like your basic divide-and-conquer

Speaking of which, that's actually how I envisioned solving this, only utilizing medians (aka, divide list, find median, then recompute new list indexes based on the median values)