You can if you're just avoiding bad luck; You often cannot if you're avoiding an active opponent - in which case, your random would need to be cryptographically

You can if you're just avoiding bad luck; You often cannot if you're avoiding an active opponent - in which case, your random would need to be cryptographically secure AND not leak any data through timing or other ways. Here's an observation: Quicksort is similarly vulnerable to an active attacker[0], and can similarly be "protected" with random pivot selection. How many quicksort implementations have you seen in production quality libraries that actually have a random pivot selection? I have seen none. As a result, I avoid quicksort (and cuckoo, and any other basic algorithm which depends on good crypto to perform well). [0] I'm not referring to McIlroy's "antiquicksort" here, which makes quicksort O(n^2) even in the presence of completely unpredictable pivot selection -- I'm assuming the data to be sorted is laid out before the sorting starts.