Qu'un algorithme ait une complexité moyenne satisfaisante n'est pas une garantie absolue d'efficacité. D'abord, parce que les données ne vérifient pas nécessairement l'hypothèse d'uniformité à partir de laquelle cette complexité moyenne a été calculée. Ensuite, l'algorithme n'est pas toujours destiné à être utilisé sur un grand nombre de données, parmi lesquelles les cas extrêmes seraient statistiquement minoritaires : un utilisateur peut systématiquement employer l'algorithme sur des mauvais cas. C'est la situation d'un jeu qui oppose le programmeur et un utilisateur malicieux de l'algorithme : le programmeur cherche à minimiser le temps d'exécution et l'utilisateur à le maximiser (pour prouver au programmeur qu'il est incompétent). Les techniques de randomisation assurent que l'utilisateur malicieux ne peut pas gagner : comme les conditions d'uniformité sont effectivement réalisées (et pas seulement supposées), les cas extrêmes sont garantis rares, inconditionnellement. Les algorithmes randomisés sont probabilistes.
Une première technique consiste à brasser le tableau au début de
l'algorithme en lui appliquant une permutation aléatoire (les 
permutations doivent être équiprobables). Cette technique est
évidemment correcte pour un problème de tri, mais s'applique
difficilement à d'autres types de problèmes.
L'autre technique a un champ d'applications plus large. Il arrive souvent qu'à une certaine étape d'un algorithme, un choix soit à faire entre plusieurs opérations (dans le tri rapide, il s'agit du choix du pivot) a priori équivalentes. Quand ce choix a été figé dans un algorithme déterministe, il se trouve que c'est un bon choix pour certaines données, et que c'est un mauvais choix pour d'autres. Un algorithme randomisé fera ce choix au hasard. Voici comment randomiser la fonction partition du tri rapide :
int rand_partition(int m, int n, int t[]) {
int p = irand(m,n);
array_swap(t, m, p);
return partition(m,n,t);
}
Il suffit de remplacer dans quicksort l'appel à partition par un appel à rand_partition.
Les algorithmes randomisés sont appelés algorithmes de Sherwood par G. Brassard et P. Bratley, en hommage à Robin des Bois.