topN using a heap

[Ivan Kazmenko via Digitalmars-d]

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.

Ivan Kazmenko.