Today was a good day

Timon Gehr via Digitalmars-d digitalmars-d at
Sat Jan 16 07:57:19 PST 2016

On 01/13/2016 04:38 AM, Andrei Alexandrescu wrote:
> On 01/12/2016 08:31 PM, Timon Gehr wrote:
> ...
>> - getPivot selects indices which depend deterministically on the range
>> length. Therefore afaics it is now possible to create inputs that force
>> quadratic runtime for topN. (E.g. an input can be crafted such that
>> getPivot always picks the third-largest element in the range.) This
>> violates the running time bound given in the documentation.
> I tried a static rng but found out that pure functions call sort().
> Overall I'm not that worried about attacks on sort().

What I'm saying is that this implementation of topN does not satisfy the 
specification. The documentation and/or the implementation should be 

More information about the Digitalmars-d mailing list