[issue11180] More efficient nlargest()/nsmallest()

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

[Raymond]
> Also, I question your assertions about running time. [...]

Interesting observation.  I wonder what the average number of comparisons actually is, for random inputs.  A quick back-of-the-envelope calculation suggests that O(max(k*log(k)*log(n), n)) might be a tighter upper bound.

Anyway, I agree with Benjamin that you (newacct) would need to implement the algorithm and demonstrate an obvious improvement.  Even then, it would be hard to swallow changing the algorithms to require O(n) space.

----------
nosy: +mark.dickinson

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue11180>
_______________________________________