Complexité moyenne du tri rapide avec choix du pivot aléatoire

Si T est un tableau de taille n et dont les éléments sont deux à deux distincts, alors le tri rapide avec choix du pivot aléatoire s'exécute en O(n*log n).