Le quicksort est en O(n*log(n)) dans le meilleur cas justement (et on espère que par un choix judicieux on arrive à s'en approcher statistiquement). Le pire cas est bel et bien en O(n*n) : ainsi si chaque découpage te conduit à avoir un sous-tableau de un élément et un sous-tableau de (k-1), alors le tri dégénère et devient équivalent à un tri à bulles.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Antoine . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 4.