Le tri comptage (Wikipedia) est le plus efficace (au delà ce serait de la divination).

Sur le principe, on détermine la place nécessaire pour les éléments puis on les places.

Dans l'exemple ci-dessous, nous avons des objets déjà trié par couleur. On souhaitent les trier par forme (nombre croissant de pointes de polygones). Les étapes sont les suivantes :

• recensement du nombre d'objet de chaque forme (ligne gris foncée du bas)
• réservation des places dans le tableau de résultat
• définition des bornes de chaque intervalle d'objets de même forme
• parcours de la liste à trier

téléchargement de l'animation