If you only want to find the median, not the fully ordered array of inputs, sorting is suboptimal. A simple trick to reduce the number of comparisons is to partition your array into values that are greater and smaller than some given test value, and then recurse the process within the 'correct' sub array.
You can find a better description of this concept - with an additional twist -
here[
^]. According to this site, the algorithm is guaranteed to be linear in time (i.e. O(N)), and therefore shouldn't have a hard time with a list of size N=10001.
Compared to that, even the best sorting algorithms are no better than O(N*log(N)) worst case, and, IIRC, at best O(N*log(log(N))) on average.
For those who don't like clicking on links from unknown sources, check google or wikipedia for "Median of medians", or take this short step by step description
Quote:
Median-of-medians Algorithm
The algorithm takes in a list and an index-median-of-medians(A, i). Assume that all elements of A are distinct (though the algorithm can be further generalized to allow for duplicate elements).
1. Divide the list into sublists each of length five (if there are fewer than five elements available for the last list, that is fine).
2. Sort each sublist and determine the median. If the list has an even number of elements, take the floor of the length of the list divided by 2 to find the index of the median.
3. Use the median-of-median algorithm to recursively determine the median of the set of all the medians.
4. Use this median as the pivot element, x. The pivot is an approximate median of the whole list and then each recursive step hones in on the true median.
5. Reorder the list such that all elements less than x are to the left of x, and all elements that are greater than x are to the right. This is called partitioning. The elements are in no particular order once they are placed on either side of x.
6. Let k be the “rank” of x meaning, for a set of numbers S, x is the kth smallest number in S.
7a. If i==k, then return x.
7b. If i<k, then recurse using median-of-medians to find the ith number of the left sub array
7c. If i>k, recurse using the median-of-medians algorithm to find the (i-k)th number of the right sub array.