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.wikiped

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 http://en.wikipedia.org/wiki/Median_of_medians