Le problème du tri, comme la plupart des problèmes, peut être appréhendé selon différentes perspectives. Une approche classique consiste à utiliser les opérateurs de comparaison tels que < ou >= définissant un ordre naturel sur les éléments à trier.

Une alternative équivalente consiste à associer à chaque objet un nombre réel, appelé clé, et l’ordre d’un ensemble d’objets correspond à l’ordre ascendant naturel défini sur leurs clés. Autrement dit, un nombre réel est attribué a chaque objet et les objets sont triés par ordre croissant de clé.

Il peut arriver que plusieurs objets soient associés à la même clé. Il s’agit d’un exemple de ce que l’on appelle un ordre partiel. En d’autres mots, il existe des paires d’éléments différents tel qu’aucun des deux éléments ne précède l’autre. Cette situation introduit une incertitude, ou en tout cas une ambiguïté, sur le résultat d’un tri si l’on ne définit pas de contrainte supplémentaire. La question est donc de savoir comment ordonner des objets de clés identiques. Ce problème est le plus souvent résolu en imposant la propriété de stabilité. Un algorithme de tri est dit stable s’il conserve l’ordre relatif original des éléments qui possèdent la même clé.

Par exemple :

Dans l’exemple précédent, la clé associée à chaque oeuvre d’H. P. Lovecraft correspond à son année d’édition. Plusieurs objets possèdent la même clé :

• 1927 The Dream Quest of Unknow Kadath et The Colour out of Space ;
• 1932 The Shadow over Innsmouth et The Dreams in the Witch-House.

The Dream Quest of Unknow Kadath doit apparaître avant The Colour out of Space dans la séquence triée afin de respecter le même ordre que la séquence initiale. De la même manière, The Shadow over Innsmouth doit être placé avant The Dreams in the Witch-House.