Are you sure in this? Once you have found a number so that exactly half of the numbers are to the left and half are to the right, couldn't you separate these two classes of numbers, sort them separately, and still get an O(N log N) time sort this way?

If I have to define median, I'd say that if you have an even number of data, any number between the two middle one is a median. This way the definition is equivalent then if you say that the median is a number whose total distance from the given numbers is minimal. This latter definition has paraleles: the mean is the number for which the square sum of its distance from the given numbers is minimal. More clearly, given the sequence (x_1, ..., x_N), the mean is the number A that minimizes the expression |x_1 - A|^2 + ... + |x_N - A|^2; the median is M if it minimizes |x_1 - M| + ... + |x_N - M|. Furthermore, informally speaking, the modus C minimizes |x_1 - C|^epsilon + ... + |x_N - C|^epsilon, where epsilon is a very small positive number.