[issue21592] Make statistics.median run in linear time

[Steven D'Aprano]

Steven D'Aprano <steve+python at pearwood.info> added the comment:

How does the performance change with this patch?

Quick-select is a nice idea in theory, but unless it is written in C, it is unlikely to beat sorting the list unless you have HUGE data sets. Its been nearly four years since I last did some benchmarks, but at the time there was no comparison, sorting was clearly much better (although Stefan found that select was faster than sorting).

In particular, all the quickselect versions I tested suffered catastrophic performance slowdowns if the data was already sorted: anything from double the time to ten times as much time.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue21592>
_______________________________________