Peux-tu nommer des algorithmes dont la complexité asymptotique est meilleure que celle du tri rapide?

Le tri rapide fonctionne en moyenne en O(n log n), ce qui est la meilleure asymptote pour les algorithmes de comparaison. Cependant, il existe des algorithmes avec une meilleure complexité asymptotique dans certains cas:

• Tri par comptage (Counting Sort) — O(n + k), où k est la plage de valeurs. Plus rapide si k n'est pas trop grand.
• Tri par base (Radix Sort) — O(d * (n + k)), où d est le nombre de chiffres, k la base du système de numération. Efficace pour trier des nombres ou des chaînes.
• Tri par fusion (Merge Sort) — garanti O(n log n), stable et prévisible.

Important : les algorithmes avec une complexité meilleure que O(n log n) ne se basent pas sur la comparaison d'éléments, mais utilisent des hypothèses supplémentaires sur les données (par exemple, plage limitée de valeurs).