Complexité algorithmique
· La complexité algorithmique temporelle dans le pire des cas permet de fixer une borne supérieure du nombre d'opérations qui seront nécessaires pour trier un ensemble de n éléments. On utilise pour symboliser cette complexité la notation de Landau : O.
· La complexité algorithmique temporelle en moyenne : c’est le nombre d'opérations élémentaires effectuées en moyenne pour trier une collection d’éléments. Elle permet de comparer les algorithmes de tris et donne une bonne idée du temps d'exécution qui sera nécessaire à l’algorithme ; on arrive à l'estimer avec une précision assez importante. Toutefois, si les ensembles à trier ont une forme particulière et ne sont pas représentatifs des n ! combinaisons possibles, alors les performances pourront être très inférieures ou très supérieures à la complexité « moyenne ».
· La complexité algorithmique spatiale (en moyenne ou dans le pire des cas) représente, quant à elle, l’utilisation mémoire que va nécessiter l'algorithme. Celle-ci peut dépendre, comme le temps d'exécution, du nombre d'éléments à trier.
Pour certains des algorithmes de tri les plus simples, T(n) = O(n2), pour les tris plus élaborés, T(n) = O(n·log(n)).
On peut montrer que la complexité temporelle en moyenne et dans le pire des cas d’un algorithme basé sur une fonction de comparaison ne peut pas être meilleure que n·log(n). Les tris qui ne demandent que n·log(n) comparaisons en moyenne sont dits optimaux.
Le problème du tri consiste, étant donné une suite u = (u1, u2, ..., un) d’éléments d’un ensemble totalement ordonné (par exemple ), à déterminer une permutation σ de 1, ..., n telle que : y = (uσ(1), uσ(2), ..., uσ(n)) soit triée. L'algorithme doit donc être en mesure de fournir toutes les possibilités de permutation des termes de la suite, car il est équivalent de fournir la permutation σ que la suite triée y. Si l’on considère que les comparaisons sont les seules opérations élémentaires, le nombre de permutations de n éléments étant n ! (factorielle n) et sachant que l’algorithme différencie deux cas à chaque comparaison, il faut que le nombre d’opérations élémentaires h soit tel que : ; ainsi, asymptotiquement, (par utilisation de la formule de Stirling).
Pour certains types de données (entiers, chaînes de caractères de taille bornée), il existe cependant des algorithmes plus efficaces au niveau du temps d'exécution, comme le tri comptage ou le tri radix. Ces algorithmes n'utilisent pas la comparaison entre éléments (la borne n·log(n) ne s'applique donc pas pour eux) mais nécessitent des hypothèses sur les objets à trier. Par exemple, le tri comptage et le tri radix s'appliquent à des entiers que l'on sait appartenir à l'ensemble [1, m] avec comme hypothèse supplémentaire pour le tri radix que m soit une puissance de 2 (c'est à dire de la forme 2k).