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