A few months ago I wrote a C implementation of a lazy "sorted" function, (https://github.com/naftaliharris/lazysort). One of the things you can use it for is computing medians, with the same "sort-then-take-the-middle-element" algorithm that the statistics module uses. Internally, however, what will happen is that the lazy data-structure that results from a call to the lazy "sorted" function will find the middle element with quickselect.

For lists of size 10M, I got a 7.3x speedup vs using the sorted function, and a 1.6x speedup vs using numpy.median. The sorted function was faster up until lists of size 100, presumably due to lower overhead. (The lazily-sorted list data-structure also keeps track of the pivots resulting from partitions, so that later method calls run faster by exploiting the partially-sorted structure that remains from earlier method calls).

Here's a plot of the time to compute the median for these different algorithms, (taken from a paper I wrote that's under review): http://imgur.com/oX1QLnS

I haven't got time at the moment, but I would consider contributing an implementation in the long run, if no one else does by then. It just shouldn't be O(n log(n)) when it doesn't have to be.

I've just spent the morning implementing various "faster" median algorithms, and it seems that constant factors, function call overhead (for recursive quickselects), etc make all alternative approaches quite slow. The sort-then-select approach is pretty damn fast, especially since I also think / am pretty sure sorted() is implemented in C...

So far I've tried median-of-medians, recursive quickselect, iterative quickselect tracking indices and partitioning in place, and heapq.nlargest. The implementation in Python 3.4.0 is both cleaner/easier to read and faster than anything I can make by an order of magnitude for 10,000 element lists. I'm sure someone else here can do better than me, but (s)he'd have a hard time beating CPython, imo.

Not only is sorting a Python list implemented in C, the algorithm was sufficiently impressive to be picked up by Java for non-primitives: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79

The reason it's for non-primitives is because it's optimized for sorting lists where comparison is relatively expensive , such as the dereferencing Python does on every item and Java does for non-primitive items.

Thanks for putting the effort in and testing it! Very interesting results.

That's very interesting. I used a C implementation of quickselect in that past that was way faster than sorting. That said, my data was also larger than 10,000 elements.

FWIW, here is some old timing data on a 2008 era Mac:

     *  approx timing on my Mac
     *          n, time in ms 
     *         10, <1
     *        100, <1
     *       1000, <1
     *      10000, <1
     *     100000, 30
     *    1000000, 230
     *   10000000, 2530
     *  100000000, 33000

You are probably right that pure python will have trouble competing with a C sort, except for quite large N.

Since this is pure Python performance you might want to give the different algorithms a try on PyPy

This might be a stupid question, but would you know where the the source for the statistics module can be found? I would be quite interested in submitting a patch, but I can't seem to find the source.

Thanks!