Imprecise running time for topN?

[Andrei Alexandrescu]

On 2/1/11 8:12 AM, Magnus Lie Hetland wrote:
> I was reading the docs for std.algorithm, when I came across topN. This
> is, of course, a highly useful problem, with several solutions; I was a
> bit surprised to see the claim that it runs in linear time. As far as I
> know, the only ways of achieving that would be (1) using the
> super-elegant, but highly inefficient, algorithm of Blum, Floyd, Pratt,
> Rivest and Tarjan, often known as Select, or (2) using soft heaps. (The
> latter, I know less about.)
>
> Checking the source, I found that -- as I suspected -- it uses the more
> common Randomized-Select (without actual randomization here, though),
> which only has an *expected* (or average-case) linear running time. It
> suffers the same worst-case problems as Quicksort.
>
> I'm not objecting to the use of algorithm -- it's a good choice in
> practice -- but the docs should probably specify that the linear
> guarantee does not hold in the worst case?

You're right (and randomization should be there, too). Could you please 
add a bugzilla entry so we don't forget about this? 
http://d.puremagic.com/issues. Thanks!

Andrei