Perhaps I misunderstand your comment, but you actually don't need to sort to compute a median (see O(n) median of medians algorithm [1]).

[1] http://en.wikipedia.org/wiki/Median_of_medians