But that adversary works by causing the sorting agent to run arbitrary, adversary-supplied code every time it makes a comparison. It has to do that because it invents the values in its list on the fly when it detects them being accessed by the sort (also, in order to detect them being accessed by the sort). That's not really the same thing. I mean, if you want to tie up a process, and you can already make it run arbitrary code that you supply, just give it something like while(1); .

If this adversary were forced to realize all the values it fed to the sorter before the sorter did any work, or if it were unable to supply its own code to the sorter, random pivot selection would be a defense.

edit:

I feel like pointing out that a quicksort implementation could defeat this adversary, without hurting its O(n log n) running time, by just comparing the first element of the sublist it was working with to every other element in the sublist -- and throwing away the results -- and then proceeding as normal. This is O(n) comparisons, which violates the vulnerability criterion of making only O(1) comparisons per call, but doesn't affect the big-O running time at all. What it does do, with an eye to this particular adversary, is realize all the values before doing any sorting work. It still doesn't fix the actual vulnerability the paper identifies, which is that you're running adversary-supplied code. I'm growing to feel like your bug report was frivolous.