You can if you&#x27;re just avoiding bad luck; You often cannot if you&#x27;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.<p>Here&#x27;s an observation: Quicksort is similarly vulnerable to an active attacker[0], and can similarly be &quot;protected&quot; 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).<p>[0] I&#x27;m not referring to McIlroy&#x27;s &quot;antiquicksort&quot; here, which makes quicksort O(n^2) even in the presence of completely unpredictable pivot selection -- I&#x27;m assuming the data to be sorted is laid out before the sorting starts.