Qu'est-ce qu'un tri? On suppose qu'on se donne une suite de 
nombres entiers 
, et on veut les ranger en ordre
croissant au sens large. Ainsi, pour 
, la suite
devra devenir
Ce problème est un classique de l'informatique. Il a été étudié en détail, cf. la moitié du livre de Knuth [29]. En tant qu'algorithme pratique, on le rencontre souvent. Par exemple, il faut établir le classement de certains élèves, mettre en ordre un dictionnaire, trier l'index d'un livre, faire une sortie lisible d'un correcteur d'orthographe, ... Il faudra bien faire la distinction entre le tri d'un grand nombre d'éléments (plusieurs centaines), et le tri de quelques éléments (un paquet de cartes). Dans ce dernier cas, la méthode importe peu. Un algorithme amusant, bogo-tri, consiste à regarder si le paquet de cartes est déjà ordonné. Sinon, on le jette par terre. Et on recommence. Au bout d'un certain temps, on risque d'avoir les cartes ordonnées. Bien sûr, le bogo-tri peut ne pas se terminer. Une autre technique fréquemment utilisée avec un jeu de cartes consiste à regarder s'il n'y a pas une transposition à effectuer. Dès qu'on en voit une à faire, on la fait et on recommence. Cette méthode marche très bien sur une bonne distribution de cartes.
Plus sérieusement, il faudra toujours avoir à l'esprit que le nombre d'objets à trier est important. Ce n'est pas la peine de trouver une méthode sophistiquée pour trier 10 éléments. Pourtant, les exemples traités dans un cours sont toujours de taille limitée, pour des raisons pédagogiques il n'est pas possible de représenter un tri sur plusieurs milliers d'éléments. Le tri, par ses multiples facettes, est un très bon exemple d'école. En général, on exigera que le tri se fasse in situ, c'est-à-dire que le résultat soit au même endroit que la suite initiale. On peut bien sûr trier autre chose que des entiers. Il suffit de disposer d'un domaine de valeurs muni d'une relation d'ordre total. On peut donc trier des caractères, des mots en ordre alphabétique, des enregistrements selon un certain champ. On supposera, pour simplifier, qu'il existe une opération d'échange ou plus simplement d'affectation sur les éléments de la suite à trier. C'est pourquoi nous prendrons le cas de valeurs entières.