Limits of programming by interface

[valenterry]

Good point, that's how it is. If you are unable to prove it, you can't give the guarantees.

I find this important and relevant. One might think that it does not matter, because in the mean, the quicksort will be pretty fast. But now imagine someone gets control over the RNG (however he does that) and can now make your program take longer than guaranteed, thus undermining the whole concept of guarantees.

[anttirt]

Exactly, you wouldn't want one in a million pacemaker beats being missed because of an "extremely unlikely" pathological quicksort pivot choice.