Classification

La classification des algorithmes de tri est très importante, car elle permet de choisir l’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci.

On distingue, tout d'abord, les algorithmes de tri d'application générale, procédant par comparaisons entre des paires d'éléments, et les algorithmes plus spécialisés faisant des hypothèses restrictives sur la structure des données entrées (par exemple, le tri par comptage, applicable uniquement si les données sont prises parmi un petit ensemble connu à l'avance). Si l'on ne précise rien, on entend habituellement par algorithme de tri un algorithme général de tri par comparaison.

Les principales caractéristiques qui permettent de différencier les algorithmes de tri sont : la complexité algorithmique, les ressources nécessaires (notamment en terme d'espace mémoire utilisé) et le caractère stable et elles se présentent comme suit :