Pour vous donner une idée de la difficulté du problème, je vous propose le petit jeu suivant. Il s'agit de trier quelques tonneaux (entre 3 et 10) par ordre de poids croissant. Le poids de chaque tonneau a été attribué aléatoirement. Utilisez le "glisser-déposer" pour déplacer les tonneaux.
Vous ne disposez que d'une balance non étalonnée vous permettant de comparer le poids des tonneaux 2 à 2 et d'étagères pouvant vous servir de stockage intermédiaire.
Ce sont exactement les mêmes éléments que ceux dont dispose un ordinateur : une fonction de comparaison et des zones de stockage.
Le but du jeu est évidemment de trier ces tonneaux en faisant le moins de comparaisons et d'échanges possibles.
| Tri par insertion (Insertion Sort) | Θ(n2) | Θ(n2) | Θ(n) | Oui | |||
| Tri par sélection ou tri par extraction (Selection Sort) | Θ(n2) | Θ(n2) | Θ(n2) | Non | |||
| Tri bulle ou tri par propagation (Bubble Sort) | Θ(n2) | Θ(n2) | Θ(n) | Oui | |||
| Tri shaker ou bidirectionnel (Cocktail Sort) | Θ(n2) | Θ(n2) | Θ(n) | Oui | |||
| Tri à peigne (Comb Sort) | |||||||
| Tri de Shell (Shell sort) | Non | ||||||
| Tri de Batcher (Batcher odd–even mergesort / Bitonic Sort) | |||||||
| Tri rapide (Quicksort) |