> If adversarial input is a concern, doing a O(n) shuffle of the data first guarantees this cannot happen. It doesn't guarantee that you avoid the worst case,

> If adversarial input is a concern, doing a O(n) shuffle of the data first guarantees this cannot happen. It doesn't guarantee that you avoid the worst case, it just removes the possibility of forcing the worst case.