topN using a heap

[Andrei Alexandrescu via Digitalmars-d]

On 01/18/2016 09:21 PM, Ivan Kazmenko wrote:
> On Tuesday, 19 January 2016 at 00:11:40 UTC, Andrei Alexandrescu wrote:
>> 4. sort was and is attackable before all of these changes
>
> No, sort utilizes Introsort (Quicksort but switch to Heapsort if recurse
> too deep): see
> https://github.com/D-Programming-Language/phobos/blob/2.067/std/algorithm/sorting.d#L1048-L1053.
> This improvement happened a year or two ago, when algorithm.d was not
> even separated into sub-modules.
>
> My adversary program (change "topN (a, MAX_N / 2)" to "sort (a)") admits
> that by not being able to slow the sort down.  But, if I comment out
> line 1053 to disable the switching, things go quadratic as expected.
>
> L1053:    depth = depth >= depth.max / 2 ? (depth / 3) * 2 : (depth * 2)
> / 3;
>
> The same remedy can help for topN: if we called partition more than log
> (length) in base (3/2) times, switch to the heap implementation of topN
> regardless of whether n is close to the edge.

Do you think sort and topN would be attackable if they used a 
per-process-seeded RNG as per Xinok's idea? -- Andrei